說起算法中的字符串畔规，需要知道幾個技巧。首當(dāng)其沖的是kmp算法，這個算法很神奇瓣蛀，子字符串是否存在于源字符串中乞娄，原本我們需要兩個for循環(huán)惧互，每次遍歷鳍刷，發(fā)現(xiàn)子字符串與源字符串不相同，就從子字符串的首個位置從新開始比較理盆，這其實很浪費時間瞻讽。
那有沒有什么方法可以不用從頭開始呢？這就要說起kmp算法了熏挎，這個算法的精髓就是要額外使用一個next數(shù)組記錄如果子字符串與源字符串不同時速勇，重新開始的位置。next數(shù)組的原理坎拐，簡單來說就是根據(jù)字符串前綴和后綴相匹配的最大長度烦磁。建議不懂的同學(xué)可以參考這篇文章养匈。
http://kb.cnblogs.com/page/176818/
下面是代碼實現(xiàn)
//獲得next數(shù)組，利用遞歸方法
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;
}
}
}
- 常用的技巧有字符串拼接
- 按字典序輸出一個字符串?dāng)?shù)組都伪，[abc,ab,de,mn]
bool cmp(string str1,string str2)
{
return str1+str2>str1+str2
}
并不是一個字符串與另一個字符串比較呕乎，還是兩個鏈接起來進(jìn)行比較。
- 查看一個str1是不是str2的旋轉(zhuǎn)后的字符串陨晶，例如“abcdef” 和 “defabc”
bool check(string str1,string str2){
string str3 = str1+str1;
return kmp(str2,str3);//利用kmp進(jìn)行判斷
}
- 除此之外還有字符串的旋轉(zhuǎn)猬仁，例如“i am a boy”轉(zhuǎn)換成“boy a am i”
- 旋轉(zhuǎn)整個字符串“yob a ma i”
- 對每個單詞進(jìn)行旋轉(zhuǎn)“boy a am i”
至于其他的字符串技巧，待續(xù)~~
