说起算法中的字符串，需要知道几个技巧。首当其冲的是kmp算法，这个算法很神奇，子字符串是否存在于源字符串中，原本我们需要两个for循环，每次遍历，发现子字符串与源字符串不相同，就从子字符串的首个位置从新开始比较，这其实很浪费时间。
那有没有什么方法可以不用从头开始呢？这就要说起kmp算法了，这个算法的精髓就是要额外使用一个next数组记录如果子字符串与源字符串不同时，重新开始的位置。next数组的原理，简单来说就是根据字符串前缀和后缀相匹配的最大长度。建议不懂的同学可以参考这篇文章。
http://kb.cnblogs.com/page/176818/
下面是代码实现
//获得next数组，利用递归方法
void getnext(char *str,int len,int next[]){
int index=1,n =0 ;//n count the next[]
next[0] = 0;
for (index = 1;index<len;index++){
while(n>0 && str[index] != str[n])
n = next[n-1];
if(str[index] == str[n])
n++;
next[index] = n;
}
}
bool kmp(char *src, char *str,int lena,int lenb)
{
int next[len];
int j=0;
getnext(str,lena,next);
for(int i=0;i<lenb;i++){
while (j>0 && src[i] != str[j])
j = next[j-1];
if (str[j] == src[i])
j++;
if (j == lena){
cout<<i-lena+1<<endl;
return true;
}
}
}
- 常用的技巧有字符串拼接
- 按字典序输出一个字符串数组，[abc,ab,de,mn]
bool cmp(string str1,string str2)
{
return str1+str2>str1+str2
}
并不是一个字符串与另一个字符串比较，还是两个链接起来进行比较。
- 查看一个str1是不是str2的旋转后的字符串，例如“abcdef” 和 “defabc”
bool check(string str1,string str2){
string str3 = str1+str1;
return kmp(str2,str3);//利用kmp进行判断
}
- 除此之外还有字符串的旋转，例如“i am a boy”转换成“boy a am i”
- 旋转整个字符串“yob a ma i”
- 对每个单词进行旋转“boy a am i”
至于其他的字符串技巧，待续~~
