#ifndef XINWEI_ROTATESTRING_H_
#define XINWEI_ROTATESTRING_H_
#include <iostream>
using namespace std;
void ReverseString(char *s,int from , int to){
char temp;
while (from <to){
temp=*(s+from);
*(s+from)=*(s+to);
*(s+to)=temp;
from++;
to--;
}
}
void LeftShiftOne(char* s,int n){
char temp=s[0];
int i=0;
while (i<n-1){
s[i]=s[i+1];
i++;
}
s[n-1]=temp;
}
/**
* (X^TY^T)^T=YX
* n字符串长度，m旋转前m位
*/
void LeftRotateString(char* s,int n,int m){
ReverseString(s,0,m-1);
ReverseString(s,m,n-1);
ReverseString(s,0,n-1);
}
void LeftRotateString2(char* s,int n,int m){
while (m--){
LeftShiftOne(s,n);
}
}
void RightRotateString(char* s,int n,int m){
ReverseString(s,0,n-m-1);
ReverseString(s,n-m,n-1);
ReverseString(s,0,n-1);
}
void ReverseWords(char* s){
ReverseString(s,0,strlen(s)-1);
int x=0;
for (int j = 0; j <strlen(s) ; ++j) {
if(s[j]==' '){
ReverseString(s,x,j-1);
x=j+1;
}
}
}
#endif
lvxinwei
字符串字母包含算法
给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数
bool StringContains(string &A, string &B)
// Created by Lv,Xinwei on 2018/2/5.
/**
* 穷举查找O(nm)
* @param A
* @param B
* @return
*/
bool StringContains(string &A, string &B) {
typedef string::const_iterator it;
int num=0;
for (it i = B.begin(); i < B.end(); i++) {
for (it j = A.begin(); j < A.end(); j++) {
if (*i == *j) {
num++;
break;
}
}
}
return num==B.length();
}
int cmp(const void* a,const void* b){
return ( *(char*)a - *(char*)b );
}
/**
* 排序查找O(nlogN+mlogM+m)
* @param A
* @param B
* @return
*/
bool StringContains2(string &A, string &B) {
sort(A.begin(),A.end());
sort(B.begin(),B.end());
typedef string::const_iterator it;
it j=A.begin();
for (it i = B.begin(); i < B.end(); i++) {
for (; j < A.end(); ) {
if (*i == *j) {
break;
}
j++;
}
if(j==A.end()){
return false;
}
}
return true;
}
/**
* 使用map O(n+m)
* @param A
* @param B
* @return
*/
bool StringContains3(string &A, string &B) {
map<int,char> bulk;
typedef string::const_iterator it;
for (it i = A.begin(); i<A.end() ; i++) {
bulk.insert(pair<char,int>(*i,1));
}
for (it i = B.begin(); i<B.end() ; i++) {
if(bulk.find(*i)==bulk.end()){
return false;
}
}
return true;
}
/**
* 使用位计算 O(n+m)
* @param A
* @param B
* @return
*/
bool StringContains4(string &A, string &B) {
int bit_counter=0;
typedef string::const_iterator it;
for (it i = A.begin(); i <A.end() ; i++) {
bit_counter|=1<<((*i)-'a');
}
for (it i = B.begin(); i <B.end() ; i++) {
if((bit_counter&(1<<((*i)-'a')))==0){
return false;
}
}
return true;
}
void testStringContain(){
string s1="aafgrsdf fsefvdgdfhfg";
string s2="absdff afsvxcvasdfc";
cout<<StringContains(s1,s2)<<endl;
s1="aafgrsdfsdfscde";
s2="absdffsdafsddafqwdfc";
cout<<StringContains2(s1,s2)<<endl;
cout<<s1<<endl;
map<char,int> bulk;
typedef map<char,int>::const_iterator it;
pair<char,int> data('s',11);
bulk.insert(data);
data={'s',100};
pair<it,bool> temp=bulk.insert(data);
cout <<temp.second<<endl;
it iii=temp.first;
cout <<iii->first<<iii->second<<endl;
s1="aafsdfsdawefscde";
s2="ab";
cout<<StringContains3(s1,s2)<<endl;
s1="aafgrsdefwfgjuytnwabcde";
s2="abgfex";
cout<<StringContains4(s1,s2)<<endl;
}
#endif //THEARTOFPROGRAMING_STRINGCONTAIN_H
最长回文串算法
给定一个字符串，求它的最长回文子串的长度。
/**
* @param s
* @param n
* @return
*/
bool IsPalindrome(const char *s, int n){
if(s== NULL||n<1){
return false;
}
for (int i = 0; i < n/2; ++i) {
if(s[i]!=s[n-i-1]){
return false;
}
}
return true;
}/**
* 穷举法遍历所有长度 O(n^3)
* @param s
* @param n
* @return
*/
int LongestPalindrome(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
int longest=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n-i;j++){
if(IsPalindrome(s+j,i)){
longest=longest<i?i:longest;
}
}
}
return longest;
}
/**
* 找中心点向外扩散 O(n^2)
* @param s
* @param n
* @return
*/
int LongestPalindrome2(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
int longest=0;//长度
//i是中心点下标
for (int i = 0; i <n ; ++i) {
//j是长度
//奇数串
for (int j = 0;(i-j)>=0&&(i+j)<n; ++j) {
if(s[i-j]!=s[i+j]){
break;
}
int c=j*2+1;
longest=longest<c?c:longest;
}
for (int j = 0;(i-j)>=0&&(i+j+1)<n; ++j) {
if(s[i-j]!=s[i+j+1]){
break;
}
int c=j*2+2;
longest=longest<c?c:longest;
}
}
return longest;
}
/**
* Manacher算法 O(n)
* @param s
* @param n
* @return
*/
int LongestPalindrome3(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
char str[n*2+4];
int j=0;
str[j++]='$';
str[j++]='#';
for (int i = 0; i < n; ++i) {
//使回文串长度变成偶数
str[j++]=*(s+i);
str[j++]='#';
}
str[j]='\0';
int p[j-1];//保存以下标为中心点的最长回文串长度
memset(p,0, sizeof(p));
int mx=0;//回文串最右边界
int idx=0;//回文串中心点
int longest=0;//最长子串
for(int i=1;i<j-1;i++){
p[i]=mx>i?min(mx-i,p[2*idx-i]):1;//2*idx-i 与i关于idx对称,如果p[2*idx-i]比mx-i长则说明p[i]>=p[2*idx-i] 短的话 p[i]=p[2*idx-i]
while(str[i-p[i]]==str[i+p[i]]){
p[i]++; //继续求p[i]的最长回文串
}
longest=p[i]>longest?p[i]:longest;
if(p[i]+i>mx){
mx=p[i]+i;
idx=i;
}
}
return longest-1;
}
squid 配置HTTPS代理
从源代码编译：（编译的squid必须是3.3或以上的版本。2.x版好像没有加密代理功能）
yum install openssl openssl-devel gcc-c++ bzip2 gcc perl
(如果你的系统是DEBIAN/UBUNTU,则需运行命令：
apt-get install openssl libssl-dev gcc g++ bzip2 perl
否则编译时，会遇到错误提示：configure: error: library ‘crypto’ is required for OpenSSL。参见
http://superuser.com/questions/371901/openssl-missing-during-configure-how-to-fix）
wget http://www.squid-cache.org/Versions/v3/3.5/squid-3.5.7.tar.bz2
tar jxvf squid-3.5.7.tar.bz2
cd squid-3.5.7
./configure --prefix=/usr --sysconfdir=/etc/squid --libdir=/usr/lib --with-openssl
--enable-basic-auth-helpers="LDAP,MSNT,NCSA,PAM,SASL,SMB,YP,DB,POP3,getpwnam,squid_radius_auth,multi-domain-NTLM" --with-swapdir=/var/spool/squid --libexecdir=/usr/lib/squid
make (此步骤耗时15分钟）
make install
配置squid,（修改SQUID的配置文件squid.conf）
然后修改Squid的配置文件。把http_port变成https_port ,修改监听的端口号为443：
https_port 443 cert=/etc/squid/public.crt key=/etc/squid/private.key
其中cert和key分别是网站的HTTPS证书和私钥。在/etc/squid/目录中，运行openssl req -x509 -nodes -days 3650 -newkey rsa:2048 -keyout private.key -out public.crt即可生成public.crt和private.key 。注意：监听的端口号必须设为443.否则squid启动不了。
chrome支持https类型的代理。启动chrome的时候在末尾加上–proxy-server=https://vps-ip:443 –ignore-certificate-errors即可。注意，把这里的vps-ip换成你的服务器的ip。
全配置好之后，用chrome浏览器即可翻墙。
证书可以用商业证书，自己生成的比较麻烦。。
启用用户认证了。
具体方法如下：yum install httpd (debian/ubuntu系统下，则apt-get install apache2)这样你的系统上就会出现htpasswd命令。然后在/etc/squid/目录里，运行htpasswd -cb /etc/squid/users jones fx5rm31s上述命令将生成密码文件users.(jones和fx5rm31s分别为你指定的用户名和密码）然后，编辑/etc/squid/squid.conf文件，在http_access deny all那一段的上方，插入：
auth_param basic program /usr/lib/squid/basic_ncsa_auth /etc/squid/users
auth_param basic children 5
auth_param basic realm Squid proxy-caching web server
auth_param basic credentialsttl 2 hours
acl normal proxy_auth REQUIRED
http_access allow normal
auth_param basic casesensitive off
然后重启squid,即可启用squid的认证机制。
前端接口防刷方法探究
暴露在前端的接口被刷是件很头疼的事，这件事情无解，根据我观察，目前主流有三种方法：
1. 通过Js注入Cookie数据，此Cookie数据会在后端进行校检，此种方式必须采用渲染Js来进行破解，提高了刷接口成本。
2. 在前端对请求参数进行加密，加密方法采用代码混淆技术，这种成本比较低，效果还不错。
3. 每次请求生成一个唯一字符串，把该字符串注入Cookie中，此串只能用一次，当访问接口时会校检该串是否有效或是否被用过，无效串直接403。
出于成本考虑我采用1和2两种方法的结合,具体流程如下：
1. 生成一个与时间戳有关系的字符串K，该字符串可采用Rc4加密算法生成，保证加密串可以被还原成时间戳。
2. 将K注入Cookie中
3. 前端拿到K，根据请求参数算出Sign
4. 前端把Sign和请求参数传递到后端，后端首先提取出K计算是否有效、是否过期了一定时间间隔，然后计算Sign是否有效
/**
* 获取与时间戳有关的加密串
* @Return String
*/
Public Static Function Getencryptionkey() {
$Timestamp = Strval(Time());
$Rc4ret = Self::Rc4(Self::Common_secret_key, $Timestamp);
Return Base64_encode($Rc4ret);
}
/**
* 从加密串中解出时间戳
* @Param $Key
* @Return String
*/
Public Static Function Decodeencryptionkey($Key) {
Return Self::Rc4(Self::Common_secret_key, Base64_decode($Key));
}
/**
* 验证加密串是否有效，考虑时间戳的失效时间。
* @Param $Key
* @Return Bool
*/
Public Static Function Checkencryptionkey($Key) {
$Nowtimestamp = Intval(Time());
If (!Empty($Key)) {
$Encyptiontimestamp = Intval(Self::Decodeencryptionkey($Key));
Return (($Encyptiontimestamp + Self::Max_valid_time_interval) >= $Nowtimestamp);
}
Return False;
}