考研的專業課以及找工作的筆試題，對于串比對模式都會有一定的考察，寫這篇部落格的目的在于進行知識的回顧與複習，友善遇見類似的題目不會糾結太多。
傳統的BF算法
傳統算法講的是串與串依次一對一的比較，舉例設目标串S=“ababcabcacb”,模式串T="abcac"，利用BF算法這個過程就會表示為：
将S串了解為數組，底标從0開始，即從a開始，第一次比對過程如下：
ok，當發現T串尚未比對結束，就開始出現了錯誤，S串坐标右移+1，開始從b比對，過程如下：
出現不同，繼續右移比對，同理，直到最後比對成功，如下：
成功之後，傳回T串出現在S串的位置即可，其算法複雜度為O(mn)。由于ＢＦ算法代碼簡單，不再贅述。
改進之後的BF算法
改進的算法思想是先将T串的末尾最後一位與S串與之對應的位置進行比較，若發現不同，則後移下一位，若相同，再從T串的第一位開始比較,其算法複雜度為O(m+n)。
KMP算法：
對于串比對問題，KMP算法最優。它改變了BF算法的回溯思路，并不是類似于BF算法一般一個一個的看，Instead，根據所求next數組的值進行移位。
KMP中next的求法：
對于上面所談到的T串，其next＝{-1,0,0,0,1}
再者，比如abcaabbac,next={-1,0,0,0,1,1,2,0,2}
aabaaa,next={-1,0,1,0,1,4}
其實呢，不用考慮那麼複雜，就是從尾到頭和從頭到尾比較，相同最長字元串的長度就是next值。
它之是以相對優化，是因為它的回溯要更省時間，當發現T[j]與S[i]不等時，就将T串右移j-next[j]個位置。
如此，便可以快速比對。具體代碼如下：
1 void GetNext(String T,int *next)
2 {
3 int i = 0, j;
4 next[0]=-1;
5 j=-1;
6 while(i<T.length-1)
7 {
8 if(j== -1 || T[i]==T[j])
9 {
10 i++;
11 j++;
12 next[i]==j;
13 }
14 else{
15 j=next[j];
16 }
17 }
18 } KMP算法如下
1 int KMP(string S,string T,int *next)
2 {
3 int i=0,j=0;
4 while(i<S.length && j<T.length)
5 {
6 if(j == -1 || S[i] ==T[i])
7 {
8 i++;
9 j++;
10 }
11 else{
12 j=next[j];
13 }
14 }
15 if(j>T.length-1)
16 return i-j+1;
17 else
18 return -1;
19 } 目前刷的面試題較少，後期繼續跟進~