一、串的定義
串是由零個和多個字元組成的有限序列，又名叫字元串。一般記為 s="a1a2a3.......an"（n>=0),其中s是串的名字，用雙引号括起來的字元序列是串的值。串中的字元長度n稱為串的長度。零個字元的串稱為空串。
還有一些概念需要解釋
子串與主串：串中任意個數的連續字元組成的子序列稱為該串的子串，相應地，包含子串的串稱為主串。子串在主串中的位置就是字串的第一個字元在主串中的序号。
二、串的比較
比如說，s=“happ” ，t=“happy”；s與t的前四位字元是一樣的，而t第五為有字元，故t>s。再比如說s=“happy”，t=“happc”；由于第五位y的ASCII值大于c的ASCII值，是以s>t;總的來說，當兩串的長度相同，且對應位置上的字元ASCII值相同，那麼這兩串才相等。怎麼判斷兩串的大小呢，判斷兩串第一處不相等的元素的ASCII值，誰的ASCII值大，那個串就大。
三、樸素的模式比對算法
又稱為“暴力比對算法”。比如說我們需要在一篇文章例找一個單詞的定位。這種子串的定位操作通常稱做串的模式比對。
假如我們需要從下面的主串S=“goodgoogle”中，找到T=“google”這個子串的位置。我們通常需要下面的步驟。
1、從主串s第一位開始，s與t的前三位“goo”比對成功，但s的第四位是‘d’，t的第四位是‘g’，是以第一位比對失敗
2、接下裡從主串s的第二位開始，主串s首字母是‘o‘，而子串t的首字母是’g‘，是以比對失敗。
3、接下來從主串的第三位開始，主串首字母是’o‘，而子串的首字母是’g‘，是以比對失敗。
4、接下來從主串的第四位開始，主串首字母是’d‘，而子串的首字母是’g‘，是以比對失敗。
5、接下來從主串的第五位開始，主串首字母是’g‘，而子串的首字母是’g‘，相同，且子串的6個字母完全比對成功，是以就能找到子串t在主串s中的位置下标為4。
代碼如下：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int Index(char* s,char* t,int lens,int lent,int* beginpos)
{
int i = *beginpos;
int j = 0;
while (i <= lens - 1&&j<=lent-1)
{
if (i <= lens - 1 && j <= lent - 1&&s[i] == t[j]) //比對成功，繼續往後比對.
{
i++;
j++;
}
else
{
i = i - j + 1; //比對失敗，則i退回到開始比對位置的下一個,j置為0。
j = 0;
}
}
if (j ==lent) //說明比對成功
{
*beginpos = i - j+1; //開始比對位置，變化為從上次子串在主串位置的下一個開始
return i - j; //将子串首字母在主串中的位置傳回。
}
else
{
return -1;
}
}
int main()
{
char s[100] = "goodgooglegoodgooglegoodgooglegoodgooglegoodgoogle";
char t[100] = "google";
int lens, lent;
lens = strlen(s);
lent = strlen(t);
int beginpos = 0;
int index;
index = Index(s, t, lens, lent, &beginpos);
while (index != -1)
{
if (index != -1)
printf("%d,", index);
index = Index(s, t, lens, lent, &beginpos);
}
puts("\b;");
return 0;
}
可以通過樸素的模式比對算法，将主串s中所有t子串的位置找出來。
可是這種算法的效率是非常低的，舉個例子。比如主串為s=“000000000000000000001“，子串t=”00001”。能想到吧，每次都要比對到子串的最後一位才會比對失敗，假設主串長度為n，子串為m。隻有當從主串的下标為n-m-1處，開始比對才能成功，其餘（n-m）*m次的比對都是失敗的，是以這也就是最壞的一種情況。此時時間複雜度為O((n-m)*m)。可想此時算法效率十分不理想。
四、KMP模式比對算法
為了解決樸素模式比對算法的低效，有三位前輩D.E.Knuth、J.H.Morrish、V.R.Pratt。發表了一個模式比對算法，可以極大的避免重複周遊的情況，我們把它稱之為克努特——莫裡斯——普拉特算法，簡稱KMP算法。
1、kmp算法原理
舉個例子假如主串S=“abcdefgab”，我們要比對的子串T=“abcdex”。如果使用前面的樸素算法，相信我們都清楚整個比對過程。比對過程如圖所示：
我們圖中給出了前六次比對。首先我們觀察T子串，發現首字母a與後面剩下的串bcdex，都不相等。也就是說a不與自己後面子串中的任何一個字元相等。那麼請看上圖中的1，子串T中的前五位字元與S中前五位字元對應相等，又因為T中的首字元a不與第2到5位的字元相等。是以T中的首字元a肯定不等于S中的第2到5位的字元。則上圖中2到5的步驟就是多餘的了，十分沒必要。是以隻需保留上圖中的1和6就好了。
假如子串T中首字元a的後面還有a字元怎麼辦呢？
請看下面的例子。假如S=“abcabcabc”，T=“abcabx”。
樸素算法比對過程如下圖：
上圖中步驟1的前五位完全相等，且T串中首字母a與第二位字元b、第三位字元c不相等。是以上圖中2、3位比較是多餘的。
又因為T串中的首字元a、第二位字元b與第四位字元b、第五位字元b相等。由于在上圖步驟1中前五位相等，故步驟4、5也是多餘的。通過上面的例子，說明了對于在子串中有與首字元相等的字元，也是可以省略一部分不必要的判斷步驟。比如省略上圖的4、5位比較
對比着兩個例子，我們發現在第一位比較時，我們的i值，即主串目前位置的下标值是6，然後進行第2、3、4、5位比較時，i值分别是2，3，4，5。到第6位比較時，i值又回到了6。即我們發現了在樸素的模式比對算法中，主串的i值是不斷的回溯，在我們的分析下這種回溯是不需要的。我們的KMP模式比對算法就是為了不讓這種沒必要的回溯出現。
既然i值不回溯，也就是不會變小，那麼要考慮的變化就是j值了。我們多次提到了子串T的首字元與自身後面字元的比較，發現如果有相等字元，j值得變化就會不相同。總的來說，j值得變化與主串無關，關鍵就取決于T串的結構中是否有重複的問題。
接着我們上面的兩個例子，在第一個例子中T=“abcdex”，T中沒有任何重複的字元，是以j就由6變成了1。而在第二個例子中，T=
”abcabx“，字首的"ab"與最後“x”之前串的字尾“ab”是相等的。是以j就由6變成了3。是以，我們可以得出規律，j值得多少取決于目前字元之前的前字尾的相似度。我們把子串T的各個位置的j值的變化定義為一個數組，那麼next的長度就是T串的長度。
首先，來了解兩個概念：“字首”和“字尾“。”字首“指除了最後一個字元外，一個字元串的全部頭部組合；”字尾“指除了第一個字元外，一個字元串的全部尾部組合。舉個例子：T="apple".
字首組合為：a，ap，app，appl。
字尾組合為：pple，ple，le，e。
我們把next數組也可以叫做部分比對表。部分比對值就是“字首”和“字尾“的最長共有元素的長度。以“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。
部分比對就是判斷子串是否有重複。比如，”ABCDAB”之中有兩個”AB”，那麼它的”部分比對值”就是2（”AB”的長度）。搜尋詞移動的時候，第一個”AB”向後移動4位（字元串長度-部分比對值），就可以來到第二個”AB”的位置。
假設一種情況，子串為T="ABCDABD";此時T的前六位“ABCDABD”已經比對成功，到第七位“D”比對失敗，然後子串向後移動的位數為6-2=4，為什麼是這個數字呢。6代表已經比對成功了的串“ABCDAB”的串長，2代表已比對成功的串的前字尾的最長共有元素的“AB”長度為2。是以将子串向後移動4位。
這就是我們為什麼需要建立部分比對表的目的，可以友善的查到已比對的串的前字尾的最長共有元素的長度（即部分比對值）。
是以我們可以得到這個子串後移公式：後移位數=已比對成功的串長-對應的部分比對值。
KMP算法最關鍵的地方就是得到部分比對表（也就是next數組），通過我們計算出的部分比對表就可以計算出當比對失敗時，j需要回溯到哪裡。用代碼實作求next數組有個十分精妙的算法。首先，設定next數組的第一個元素next[0]為-1。定義兩個變量i=-1、j=0。如果i==-1或第i個和第j個相等時，next[++j]=++i；否則的話将i置為-1；這個過程就是前字尾的比較過程，舉個例子，目前字尾的最大公共長度為1時，i與j往後移一位，如果i與j相等那麼這時的最大公共元素長度就是2，否則比對失敗，此時i與j不後移，将i置為-1。等于終端需要重新比對，然後再次進入循環，判斷當i==-1，此時i等于-1，因為j所在處比對失敗，是以此時比對值為i++為0。第一次看代碼可能看不懂，需要多看幾遍代碼方能了解為何要将next[0]設為-1。
循環結束後，将next[0]又置為0，因為下标為0的元素是串中的第一個元素。之前無字元串，是以部分比對值為0。循環開始時設定next數組的第一個元素next[0]為-1，隻是為了友善計算部分比對值表。計算完成後，next的每一個元素下标都對應子串T中的每一個元素的下标。同樣的子串中下标為j的元素，在next數組裡面對應的部分比對值，就是next[j]。舉個例子，當在子串T下标為j處比對失敗時，根據KMP算法我們需要j後移，此時j對應的部分比對值為next[j],是以j需要後移的位數是：j-next。
void GetNext(char* t,int* next,int lent)
{
int i, j;
j = 0;
i = -1;
next[0] = -1; //設定第一個值為-1。
while (j<lent)
{
if (i == -1 || t[i] == t[j])
{
next[++j] = (++i);
}
else
i = next[i];
}
next[0] = 0; //将j=0時，的部分比對值改為0。
}
int Index_KMP(char* s, char* t, int lens, int lent, int* beginpos)
{
int i, j;
i = *beginpos;
j = 0;
int next[100];
GetNext(t,next,lent);
while (i<lens&&j<lent)
{
if (s[i] == t[j])
{
i++;
j++;
}
else
j -= j - next[j]; //由後移位數=已比對串長（j）-部分比對值next[j]，計算出j移到哪裡去。
if (j==0&&s[i]!=t[j]) //由于j回溯到0，如果不進行操作的話會陷入死循環，故當因比對失敗後j回溯到0後，需要将主串的目前位置下标i向後移一位開始新的比對。
{
i++;
}
}
if (j == lent)
{
*beginpos = i - j + 1 + 1;
return i - j;
}
else
return -1;
}
KMP算法與樸素的模式比對算法不同的地方在于：KMP算法不需要主串目前位置下标i回溯，i隻管前進，而需要根據部分比對值來确定j需要回溯到哪。在有些比對問題上，性能明顯好于樸素的模式比對算法。
代碼中将有些關鍵步驟進行了注釋，若還有不懂的地方，請留言。将會進行回複。
打字不易，請多多點贊。