一、簡介
在說改進的模式匹配（KMP）算法之前我們先說樸素的模式匹配：
其實很簡單沫勿，就是兩個字符串逐位比較挨约。在模式匹配中：我們假定字符串P在字符串T中查找是否有匹配的。此時产雹，稱P為模式（Pattern）字符串诫惭，稱T為目標（Target）字符串。
OK蔓挖，我一般比較喜歡以實例說明問題夕土。
T: a b d a b d a b c
P: a b d a b c
樸素的模式匹配算法
樸素的模式匹配算法就是用P和T依次比較，即為：
第一趟比較：
T: a b d a b d a b c
P: a b d a b c
發(fā)現第6個元素（下標為5）d和c不相等瘟判，第一趟結束怨绣，此時比較了6次（6個元素）。
第二趟比較：
T: a b d a b d a b c
P: a b d a b c
第一個元素就不相等荒适，第二趟結束梨熙，此時比較了1次（1個元素）。
第三趟比較：
T: a b d a b d a b c
P: a b d a b c
第一個元素就不相等刀诬，第三趟結束咽扇，此時比較了1次（1個元素）。
第四趟比較：
T: a b d a b d a b c
P: a b d a b c
第一個元素相等陕壹，第二個元素也相等质欲，第三、四糠馆、五嘶伟、六都相等，匹配成功又碌，第四趟結束九昧，此時比較了6次（6個元素）绊袋。
匹配成功，共比較14次铸鹰。但是這個是我們理想狀態(tài)下的匹配方案癌别，實際中字符串的長度遠遠不止這些。這種算法是一種帶回逆的算法蹋笼，成為樸素的模式匹配算法展姐。
改進的模式匹配（KMP）算法
KMP算法就是消除了樸素匹配的回逆，利用一個失效函數（failure function）替代直接的回逆剖毯。思路如下：
第一趟比較：
T: a b d a b d a b c
P: a b d a b c
發(fā)現第6個元素（下標為5）d和c不相等圾笨。此時，進入一個P串的處理：
此時取出P串逊谋， a b d a b c 因為是c不和d不匹配擂达，去掉此項，獲得
a b d a b
此時判斷 a b d a 是否與 b d a b 相等涣狗？ 不等谍婉，進入下一輪判斷
此時判斷 a b d 是否與 d a b 相等？ 不等镀钓，進入下一輪判斷
此時判斷 a b 是否與 a b 相等？ 相等镀迂，結束第一趟總體判斷丁溅。
（先不要急，接下來我就會說為什么這樣匹配和這樣匹配的用途Ｌ阶瘛）
然后直接拿d和字符串中不匹配的那一項進行比較窟赏。
以上就是KMP的流程，為什么要這樣做箱季？在一些串中涯穷，目標串會遠遠長于模式串，如果每次都江模式串和目標串一一比較藏雏。此時時間復雜度當增加拷况，而且在模式串中會出現很多的無效匹配，相當于無用功掘殴。但是假如先在模式串中進行比較赚瘦，因為模式串會遠遠短于目標串，所以會相當減少時間復雜度奏寨。
二起意、next數組的理解
對于KMP算法來說，重點就是 next數組 （也有叫覆蓋函數病瞳，部分匹配表揽咕，lps數組等）悲酷。
總之就是 對模式串做預處理，而且該預處理只和 模式串(pattern)本身有關亲善！
假設有模式串 pattern = “abababca”; 則有匹配表：
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
下面介紹《部分匹配表》是如何產生的舔涎。
首先，要了解兩個概念：”前綴”和”后綴”逗爹。 “前綴”指除了最后一個字符以外亡嫌，一個字符串的全部頭部組合；”后綴”指除了第一個字符以外掘而，一個字符串的全部尾部組合挟冠。
字符串: "bread"
前綴： b , br, bre, brea
后綴: read, ead, ad , d
關于 next數組 （也有叫覆蓋函數，部分匹配表袍睡，lps數組） 的通俗解釋：”部分匹配值”就是”前綴”和”后綴”的最長的共有元素的長度知染。以”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锯仪。
下面舉個例子
pattern “AABAACAABAA”, next[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
pattern “ABCDE”, next[] is [0, 0, 0, 0, 0]
pattern “AAAAA”, next[] is [0, 1, 2, 3, 4]
pattern “AAABAAA”, next[] is [0, 1, 2, 0, 1, 2, 3]
pattern “AAACAAAAAC”, next[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
代碼如下：
/*
* function 生成部分匹配表泵督，next數組
* param subStr 模式串，子串
* param next next數組庶喜，部分匹配信息表
* param len next數組的長度小腊，一般就是模式串的長度
* return 無
*/
void GetNext(const char* subStr, int* next, int len)
{
memset(next, 0, len);
int prefix = -1; //前綴
int suffix = 0; //后綴
next[0] = -1; //第一個元素只是用來控制prefix和suffix后移的
while (suffix < len - 1)//當比較到最后一個字符的時候退出循環(huán)
{
/*
當prefix == -1的時候表示要從prefix=0救鲤，suffix=1開始比較
若prefix ！= -1秩冈，表示前綴和后綴已經有重合的了本缠，接著往后移比較
例如：subStr="ABABABB"
1.prefix=-1,往后移，prefix=0入问，suffix=1丹锹，next[1] = 0,表示字符串‘A’前綴后綴無重合
2.prefix=0,比較subStr[0]和subStr[1]('A'和'B'),不相等，把prefix重新置為next[prefix](next[0]==-1)
3.prefix=-1,往后移芬失，prefix=0楣黍，suffix=2，next[2] = 0,表示字符串‘AB’前綴后綴無重合
4.prefix=0棱烂，比較subStr[0]和subStr[2]('A'和'A'),相等租漂，繼續(xù)往后移，prefix=1颊糜，suffix=3哩治，next[3]=1
表示字符串"ABA"有一個字符前綴后綴相等('A'和'A')
5.prefix=1，比較subStr[1]和subStr[3]('B'和'B'),相等衬鱼，繼續(xù)往后移业筏，prefix=2，suffix=4,next[4]=2
表示字符串"ABAB"有兩個字符前綴后綴相等('AB'和'AB')
6.prefix=2馁启，比較subStr[2]和subStr[4]('A'和'A'),相等驾孔，繼續(xù)往后移，prefix=3惯疙，suffix=5,next[5]=3
表示字符串"ABABA"有三個字符前綴后綴相等('ABA'和'ABA')
7.prefix=3，比較subStr[3]和subStr[5]('B'和'B'),相等妖啥，繼續(xù)往后移霉颠，prefix=4，suffix=6,next[6]=4
表示字符串"ABABAB"有四個字符前綴后綴相等('ABAB'和'ABAB')
8.當suffix=6最后一個的時候荆虱，就不需要比較了蒿偎，因為KMP算法中最后一個并無指導匹配的作用,因為一旦前6個匹配成功，最后一個
就算不成功怀读，用到的也是前一個的部分匹配信息诉位，若是成功那就直接返回了，所以求next數組的時候菜枷，最后一個的信息省略
*/
if (prefix == -1 || subStr[prefix] == subStr[suffix])
{
++prefix, ++suffix;
next[suffix] = prefix;
printf("%d ", next[suffix]); //測試用苍糠，可刪除
}
else
prefix = next[prefix];
}
printf("\n"); //測試用，可刪除
}
三啤誊、KMP模式匹配算法
int Index_KMP(char *s,char *p,int pos,int next[])
/*利用模式串p的next函數岳瞭，求p在主串中從第pos個字符開始的位置*/
/*若匹配成功拥娄，則返回模式串在主串中的位置（下標），否則返回-1瞳筏。設模式串第一個字符的下標為0*/
{
int i,j,slen,plen;
i = pos-1;
j=-1;
slen = strlen(s);plen = strlen(p);
while(i<slen&&j<plen){
if(j==-1||s[i]==p[j]){++i;++j;}
else j = next[j];
}
if(j>=plen)return i-plen;
else return -1;
