BF算法
算法思想：
比較簡單，定義i，和j分别指向主串和字串的頭部），依次向後比較，若比較失敗，主串和字串都需要回溯（i=比較輪數+1的位置，j回到0位置）
元素相同，故i，j均向後移一位
元素不同，i退回第二個位置。j變成0
元素還是不同，i退到第三個位置
結束
#include<stdio.h>
#include<string.h>
bool BF(char a[],char b[]){
int index1 = 0;//指向a的頭部
int index2 = 0;//指向b的頭部
for(int i = 0;i<strlen(a);i++){//輪數
if(a[index1]==b[index2]){
index1++;
index2++;
}else{
index1 = i+1;
index2 = 0;
}
if(index2==strlen(b)) return true;
}
return false;
}
int main(){
char a[6] = {'a','c','a','b','d','a'};
char b[3] = {'a','b','d'};
char c[3] = {'a','b','e'};
if(BF(a,b))printf("比對\n");
else printf("不比對\n");
if(BF(a,c))printf("比對\n");
else printf("不比對\n");
return 0;
}
KMP算法
BF算法的弊端：
每次j下标都要回到0号下标，當主串和字串比對失敗時，主串進行回溯會影響效率，回溯之後，主串與字串有些部分比較是沒有必要的
以下圖為例，當i=j=5的時候比對失敗
按照BF算法，i=1，j=0，但這顯然是多餘的，因為子串第一個字元是A，令主串指針回溯到B的位置沒有必要
（主串前六個字元我們都是通路過的），隻需要令i=3，j=0就可以繼續比較了。
更進一步，子串第二個字元是B，而i=4剛好指向B，那麼可以令i = 4，j = 1
同理可以令i = 5，j = 2
我們發現i和最初沒有變化，隻有j的位置變化了
整個KMP的重點就在于當某一個字元與主串不比對時，我們應該知道j指針要移動到哪
事先我們會計算每個字串【0，k】的字首和字尾公共部分的最大長度，資訊儲存在next數組中。一旦比對失敗，就調取這個子串【0，i-1】的next數組資訊（假設i下标時比對失敗），j移動
因為這個重疊部分之前已經比較過了，不用再次比較
算法實作
next數組
next數組是字元串每一位及之前的字元串中，字首和字尾公共部分的最大長度的集合
next[i]儲存的是string中前i+1位字元串字首和字尾的最長長度
比如ptr字元串(abxabwabxad)，那麼next數組就有11個元素
next[0]=-1（無前字尾）
next[1]=0（ab無公共前字尾）
next[2]=0(abx中無公共前字尾)
next[3]=1(abxa公共前字尾最長為a，長度為1)
next[4]=2(abxab公共前字尾最長為ab，長度為2)
next[5]=0(abxabw中無公共前字尾)
next[6]=1(abxabwa公共前字尾最長為a，長度為1)
next[7]=2(abxabwab公共前字尾最長為ab，長度為2)
next[8]=3(abxabwabx公共前字尾最長為abx，長度為3)
next[9]=4(abxabwabxa公共前字尾最長為abxa，長度為4)
next[10]=0(abxabwabxad中無公共前字尾)
注：字首是第一個元素到倒數第二個元素
字尾是第二個元素到倒數第一個元素
next數組求法，是自身與自身的比對
求next【k】，k=0，1，2，。。。，N
取第一個串的後半部分（int）（k/2）個數
和第二個串前一部分
如求下面一個串的next【6】:這裡先不讨論next數組求法，最後再分析
#include<stdio.h>
#include<string.h>
void getNext(char a[],int *next){
next[0]=-1;
int k = -1;
for (int q = 1; q < strlen(a); q++)
{
while (k > -1 && a[k + 1] != a[q])
{
k = next[k];//往前回溯
}
if (a[k + 1] == a[q])//如果相同，k++
{
k = k + 1;
}
next[q] = k;
}
}
bool KMP(char a[],char b[]){
int next[strlen(a)];
getNext(a,next);
int i = 0;
int j = 0;
int len1 = strlen(a);
int len2 = strlen(b);
while(i<len1&&j<len2){
if(a[i]==b[j]||j==-1){ //注意一定要j = -1，前後公共部分長度為0，就沒有必要回溯了
i++;
j++;
}else{
j = next[j];
}
}
// printf("%d,%d ",i,j);
if(j==strlen(b)) return true;
return false;
}
int main(){
char a[] = "abacababa";
int next[strlen(a)];
getNext(a,next);
//for(int i = 0;i< strlen(a);i++)printf("%d ",next[i]);
char b[] = "cba";
char c[] = "ca";
char d[] = "baba";
if(KMP(a,b))printf("比對\n");
else printf("不比對\n");
if(KMP(a,c))printf("比對\n");
else printf("不比對\n");
if(KMP(a,d))printf("比對\n");
else printf("不比對\n");
return 0;
}
這裡很難了解的點是
while (k > -1 && str[k + 1] != str[q])
{
k = next[k];
}
從代碼上看：我們往前找到一個k，使a[k + 1]==a[q]
為什麼要找這個：因為要找前字尾的新的公共部分，a[k+1]是字首的公共部分+1，a[q]是原來字尾的最後一個+1(即新增的元素)
注意；這裡的公共部分是上一次求出的，也就是最後一個是a（用遞歸的思想去了解，我們不關注前面具體怎麼來的）
為什麼要回溯：因為比對不對了–》是以現有的字首和字尾公共長度是0？
這顯然是不對的，你不能保證這個串字首完全沒有能和字尾比對的部分。
比如這個求next【7】，最後一個數不同，是不是意味着公共長度為0？顯然不一定（我怎麼知道前面有沒有C出現?）
這個時候我們需要回溯到前面找到C
回溯不一定是k–（這樣太麻煩，而且據說會出錯）
看黃色的部分字首字尾重疊部分是ABA，長度為3，那麼next【k】=2，回溯一次（用于比較的是a【k+1】）
還不同，還需要回溯，現在黃色部分是aba，前字尾重疊部分為a，那麼next【k】=0，回溯一次（用于比較的是a【k+1】）
還不同，繼續回溯重疊部分為0，那麼next【k】=-1；
舉一個更明顯的例子
雖然不比對了，但是明顯還有公共的部分【a，g】
結合整體代碼總結一下
for (int q = 1; q < strlen(a); q++)
{
while (k > -1 && a[k + 1] != a[q])
{
k = next[k];//往前回溯
}
if (a[k + 1] == a[q])//如果相同，k++
{
k = k + 1;
}
next[q] = k;
}
循環求next數組，q是最後一位，而k是字首的公共部分的最後一個（上一次求出的）的下一個，如果這個數和a【q】相等，那麼公共部分長度可以加1（因為原來字首字尾公共部分長度是K，現在字尾多了一個元素，去判斷公共部分以外的第一個元素是否與這個元素重合），否則我們進行回溯，直到找到一個新的（更小的）公共部分