引言：關于字元串
字元串(string)：是由0或多個字元組成的有限序列。一般寫作`s = "123456..."`。s這裡是主串，其中的一部分就是子串。
其實，對于字元串大小關系不如是否相同重要。包括密碼驗證、hash列等。
而字元串的存儲結構有兩種：順序存儲結構和鍊式存儲結構。由于不同的字元是連在一起的，是以一般是開足夠大的空間進行順序存儲，這樣更符合字元串的意義。
一、BF算法實作
一種暴力的、樸素的模式比對算法，是的，時間複雜度為O(M*N)。而下面的KMP算法則是O(M+N)。不廢話，直接上代碼。
1 int BFfind(string base,string target,int start=0){
2 if(base.length()<1 || target.length()<1 || start<0)
3 return -1;
4 int i,j;
5 for(i=start;i<base.length();++i){
6 for(j=0;j<target.length();++j){
7 if(target[j]==base[i+j])
8 continue;
9 else
10 break;
11 }
12 if (j==target.length()){ //完全比對
13 return i;
14 }
15 }
16 return -1; //沒找到
17 } 二、KMP算法實作思路
來自：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
舉例來說，有一個字元串"BBC ABCDAB ABCDABCDABDE"，我想知道，裡面是否包含另一個字元串"ABCDABD"？
許多算法可以完成這個任務，Knuth-Morris-Pratt算法（簡稱KMP）是最常用的之一。它以三個發明者命名，起頭的那個K就是著名科學家Donald Knuth。
這種算法不太容易了解，網上有很多解釋，但讀起來都很費勁。直到讀到Jake Boxer的文章，我才真正了解這種算法。下面，我用自己的語言，試圖寫一篇比較好懂的KMP算法解釋。
1.
首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜尋詞"ABCDABD"的第一個字元，進行比較。因為B與A不比對，是以搜尋詞後移一位。
2.
因為B與A不比對，搜尋詞再往後移。
3.
就這樣，直到字元串有一個字元，與搜尋詞的第一個字元相同為止。
4.
接着比較字元串和搜尋詞的下一個字元，還是相同。
5.
直到字元串有一個字元，與搜尋詞對應的字元不相同為止。
6.
這時，最自然的反應是，将搜尋詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜尋位置"移到已經比較過的位置，重比一遍。
7.
一個基本事實是，當空格與D不比對時，你其實知道前面六個字元是"ABCDAB"。KMP算法的想法是，設法利用這個已知資訊，不要把"搜尋位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。
8.
怎麼做到這一點呢？可以針對搜尋詞，算出一張《部分比對表》（Partial Match Table）。這張表是如何産生的，後面再介紹，這裡隻要會用就可以了。
9.
已知空格與D不比對時，前面六個字元"ABCDAB"是比對的。查表可知，最後一個比對字元B對應的"部分比對值"為2，是以按照下面的公式算出向後移動的位數：
移動位數 = 已比對的字元數 - 對應的部分比對值
因為 6 - 2 等于4，是以将搜尋詞向後移動4位。
10.
因為空格與Ｃ不比對，搜尋詞還要繼續往後移。這時，已比對的字元數為2（"AB"），對應的"部分比對值"為0。是以，移動位數 = 2 - 0，結果為 2，于是将搜尋詞向後移2位。
11.
因為空格與A不比對，繼續後移一位。
12.
逐位比較，直到發現C與D不比對。于是，移動位數 = 6 - 2，繼續将搜尋詞向後移動4位。
13.
逐位比較，直到搜尋詞的最後一位，發現完全比對，于是搜尋完成。如果還要繼續搜尋（即找出全部比對），移動位數 = 7 - 0，再将搜尋詞向後移動7位，這裡就不再重複了。
14.
下面介紹《部分比對表》是如何産生的。
首先，要了解兩個概念："字首"和"字尾"。 "字首"指除了最後一個字元以外，一個字元串的全部頭部組合；"字尾"指除了第一個字元以外，一個字元串的全部尾部組合。
15.
"部分比對值"就是"字首"和"字尾"的最長的共有元素的長度。以"ABCDABD"為例，
－ "A"的字首和字尾都為空集，共有元素的長度為0；
－ "AB"的字首為[A]，字尾為[B]，共有元素的長度為0；
－ "ABC"的字首為[A, AB]，字尾為[BC, C]，共有元素的長度0；
－ "ABCD"的字首為[A, AB, ABC]，字尾為[BCD, CD, D]，共有元素的長度為0；
－ "ABCDA"的字首為[A, AB, ABC, ABCD]，字尾為[BCDA, CDA, DA, A]，共有元素為"A"，長度為1；
－ "ABCDAB"的字首為[A, AB, ABC, ABCD, ABCDA]，字尾為[BCDAB, CDAB, DAB, AB, B]，共有元素為"AB"，長度為2；
－ "ABCDABD"的字首為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，字尾為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。
16.
"部分比對"的實質是，有時候，字元串頭部和尾部會有重複。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分比對值"就是2（"AB"的長度）。搜尋詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分比對值），就可以來到第二個"AB"的位置。
三、KMP算法的代碼實作
首先是Next數組的代碼：重要的思路是在不比對的時候怎麼進行回溯（第6、7行）。
1 void GetNext(string target,int *next){
2 int index,k;//k:最大字尾長度 ;index:字元串下标
3 int len = target.length();
4 next[0] = 0;
5 for(index=1,k=0;index<len;++index){
6 while(k>0 && target[index]!=target[k])
7 k= next[k-1];//回溯找到長度為k-1的最大字尾
8 if(target[index]==target[k])
9 ++k;
10 next[index] = k;
11 }
12 } 然後是KMP的主體部分。這裡用兩重循環實作的，為了讓代碼易懂，是以多開了幾個變量來增強可讀性，比如說：用來存放長度變量等
最重要的地方是運用了之前提到的 “移動位數 = 已比對的字元數 - 對應的部分比對值“ 這個公式。
1 int KMPfind(string base,string target){
2 int *next = new int [target.length()];
3 GetNext(target,next);
4
5 int m = base.length(), n=target.length();//m,n分别為base和target的長度
6 int step;//移動步數
7 int num = 0;//已經比對的字元數
8 int i,j;
9 for(i=0;i<m;){
10 num = 0;
11 for(j=0;j<n;++j){
12 if(target[j]==base[i+j])
13 ++num;
14 else
15 break;
16 }
17 if (num==n){
18 return i;
19 }
20 if(num)
21 step = num-next[num-1];
22 else
23 step = 1;
24 //cout<<"i is:"<<i<<"step is:"<<step<<endl;
25 i = i+step;
26 //cout<<"i is:"<<i<<"step is:"<<step<<endl;
27 }
28 return -1;
29 }