KMP 匹配算法是由 "Knuth Morris Pratt" 提出的一種快速的模式匹配算法。
hint：不為自身的最大首尾重復(fù)子串長度
1.待解決的問題：假設(shè)P為給定的子串，T是待查找的字符串，要求從T中找出與P相同的所有子串，這稱為模式匹配問題。 (可以給出子串在T中的位置) (下文中提到的P和T分別為子串和目標(biāo)串)
讓我們先來看個(gè)例題：
T: t0 t1 t2 t3 .... tm-1 ... tn-1
P: p0 p1 p2 p3 .....pm-1
從T的最左邊開始比較，使得 TK = PK，則匹配成功。
2.解決模式匹配問題的方案：
A：樸素的模式匹配算法(思路簡單,但不夠簡便，時(shí)間長，有回溯)：最簡單和最直接的做法，用P中的字符依次與T中的字符進(jìn)行比較，遇到不相等的字符，則可將P右移一個(gè)字符，重新進(jìn)行比較，直到某次匹配成功或者到達(dá)P的最右字符移出T為止。
如：若P="aaaba", T="aaabbaaaba", 則匹配過程如下圖
T: a a a b b a a a b a
P: a a a b a
a a a b a
.....
a a a b a
從上不難分析，最壞的情況是“每次比較都在最后一個(gè)字符出現(xiàn)不等，每趟最多比較M次，最多比較N-M+1趟，總的比較次數(shù)最多為M*(N-M+1)” ，時(shí)間復(fù)雜性為0(M*N)。 在P右移一位時(shí)，不管上一趟比較的中間結(jié)果是什么，因此回溯是不可避免的(如：前3個(gè)aaa 不需要一位一位的移 ) 。下面我來介紹無回溯的KMP算法。
3.KMP算法解決匹配中哪些主要問題：
A.當(dāng)字符串比較出現(xiàn)不等時(shí)，確定下一趟比較前，應(yīng)該將P右移多少個(gè)字符；
B. P右移后，應(yīng)該從哪個(gè)字符開始和T中剛才比較時(shí)不等的那個(gè)字符繼續(xù)開始比較。
我們通過樸素模式匹配的例子來引出問題。在第一次比較過程中失敗的是P的第4個(gè)字符b，這表明P的前4個(gè)字符是成功的。模式P的第3個(gè)字符b在它的前3個(gè)字符(aaa)中并未出現(xiàn)。因此，在下一次比較時(shí)候，至少要將P向后移4個(gè)字符；再看P的第一個(gè)字符與最后一個(gè)字符是相同的，因此將P右移4個(gè)字符后，再從第一個(gè)字符比較，肯定也是不等的。綜上所訴：應(yīng)該將P右移5個(gè)字符，再從P的第0個(gè)字符和T的第5個(gè)字符開始比較！
KMP算法核心：KMP算法借助于一個(gè)輔助數(shù)組next來確定當(dāng)匹配過程中出現(xiàn)不等時(shí)，模式P右移的位置和開始比較的位置。next[i]的取值只與模式P本身的前i+1項(xiàng)有關(guān)，而與目標(biāo)T無關(guān)。匹配過程中遇到Pi不等于Tj時(shí)，若next[i]>=0，則應(yīng)將P右移i-next[i]位個(gè)字符，用P中的第next[i]個(gè)字符與Tj 進(jìn)行比較；若：next[i]= -1，P中的任何字符都不必再與Tj比較，而應(yīng)將P右移i+1個(gè)字符，從P0和Tj+1從新開始下一輪比較(可能不太好理解，自己找個(gè)例子，對(duì)著話一句一句試試看)
因此只要計(jì)算出與模式P相關(guān)的next數(shù)組，按上面的含義，就可以很容易地給出串的匹配算法。(問題就這樣轉(zhuǎn)化了)
C.next的計(jì)算：以P = " 01001010100001"為例。
i : 0 1 2 3 4 5 6 .....
P : 0 1 0 0 1 0 1 .....
j(next[i]) : -1 0 0 1 1 2 3 .....
如1：我們要算next[2]的值,有關(guān)的為P本身的前2個(gè)字符0,1。在字符串01中，尋找出“左右相同的最大字符串，此字符串所含字符的個(gè)數(shù)就為next[i]的值”而0不等于1，相同字符串不存在，所以next[i] = 0；
如2：我們要算next[6]的值，有關(guān)的為P本身前6個(gè)字符010010 。此字符串中010 = 010左右相同的最大字符串為010，個(gè)數(shù)為3。所以next[i]=3；
如3：我們要算next[5]的值，有關(guān)的為P本身前5個(gè)字符01001。此字符串中 01=01 左右相同的最大字符串為01，個(gè)數(shù)為2。所以next[i]=2；
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
FILE *fin=fopen("test.in","r");
FILE *fout=fopen("test.out","w");
char s1[200],s2[200];
int next[200];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
void getnext()
{
memset(next,0,sizeof(next));
int i=-1,j=0;
next[0]=-1;
while(j<strlen(s2))
{
if(i==-1||s2[i]==s2[j]){
i++; j++;
next[j]=i;
}
else i=next[i];
}
}
int KMP()
{
int i=0,j=0,len1=strlen(s1),len2=strlen(s2);
while((i<len1)&&(j<len2))
{
if(j==-1||s1[i]==s2[j]) {j++;i++;}
else j=next[j];
}
if(j==len2) return i-len2;
else return -1;
}
int index_KMP()
{
int i=0,j=0,len1=strlen(s1),len2=strlen(s2),re=0;
while(i<len1&&j<len2)
{
if(j==-1||s1[i]==s2[j]) {i++;j++;}
else j=next[j];
re=max(re,j);
}
return re;
}
int main()
{
fscanf(fin,"%s",s1);
for(int i=1;i<=3;i++)
{
fscanf(fin,"%s",s2);
getnext();
fprintf(fout,"%d %d\n",KMP(),index_KMP());
}
return 0;
}