KMP：給出兩個(gè)字符串A（稱為模板串）和B（稱為子串），長(zhǎng)度分別為lenA和lenB，要求在線性時(shí)間內(nèi)，對(duì)于每個(gè)A[i]（0<=i<lenA)，求出A[i]往前和B的前綴匹配的最大匹配長(zhǎng)度，記為ex[i]（或者說(shuō)，ex[i]為滿足A[i-z+1..i]==B[0..z-1]的最大的z值）。KMP的主要目的是求B是不是A的子串，以及若是，B在A中所有出現(xiàn)的位置（當(dāng)ex[i]=lenB時(shí)）。
【算法】
設(shè)next[i]為滿足B[i-z+1..i]==B[0..z-1]的最大的z值（也就是B的自身匹配）。設(shè)目前next[0..lenB-1]與ex[0..i-1]均已求出，要用它們來(lái)求ex[i]的值。
根據(jù)ex的定義，有A[i-1-ex[i-1]+1..i-1]==B[0..ex[i-1]-1]，這時(shí)，若有A[i]==B[ex[i-1]]，則可以直接得到ex[i]=ex[i-1]+1（因?yàn)閕-1-ex[i-1]+1即i-ex[i-1]，現(xiàn)在由于A[i]==B[ex[i-1]]，可得A[i-ex[i-1]..i]==B[0..ex[i-1]]，即A[i-ex[i-1]+1-1..i]==B[0..ex[i-1]+1-1]，所以ex[i]=ex[i-1]+1）。若A[i]!=B[ex[i-1]]？
設(shè)j=next[ex[i-1]-1]，則根據(jù)next定義得B[ex[i-1]-j..ex[i-1]-1]==B[0..j-1]，又因?yàn)锳[i-ex[i-1]..i-1]==B[0..ex[i-1]-1]得A[i-j..i-1]==B[ex[i-1]-j..ex[i-1]-1]，這樣有
A[i-j..i-1]==B[0..j-1]！也就是此時(shí)只需再比較A[i]與B[j]的值是否相等即可，若相等，可得ex[i]=j+1，若仍不相等，則更新j為next[j-1]，繼續(xù)比較A[i]與B[j]是否相等……直到A[i]與B[j]相等或直到j(luò)==0時(shí)，A[i]仍不等于B[j]，此時(shí)ex[i]=0。邊界：求ex[0]時(shí)，初始j（用來(lái)代替ex[i-1]）為0。
現(xiàn)在還有一個(gè)問(wèn)題，如何求next？顯然next就是以B自身為模板串，B為子串的“自身匹配”，用類似的辦法即可，唯一不同的是next[0]=lenB可以直接得到，求next[1]時(shí)，初始j（代替next[i-1]）為0。
【核心代碼】
lenA = strlen(A); lenB = strlen(B);
next[0] = lenB;
int j = 0;
re2(i, 1, lenB) {
while (j && B[i] != B[j]) j = next[j - 1];
if (B[i] == B[j]) j++;
next[i] = j;
}
j = 0;
re(i, lenA) {
while (j && A[i] != B[j]) j = next[j - 1];
if (A[i] == B[j]) j++;
ex[i] = j;
}
擴(kuò)展KMP：給出模板串A和子串B，長(zhǎng)度分別為lenA和lenB，要求在線性時(shí)間內(nèi)，對(duì)于每個(gè)A[i]（0<=i<lenA)，求出A[i..lenA-1]與B的最長(zhǎng)公共前綴長(zhǎng)度，記為ex[i]（或者說(shuō)，ex[i]為滿足A[i..i+z-1]==B[0..z-1]的最大的z值）。擴(kuò)展KMP可以用來(lái)解決很多字符串問(wèn)題，如求一個(gè)字符串的最長(zhǎng)回文子串和最長(zhǎng)重復(fù)子串。
【算法】
設(shè)next[i]為滿足B[i..i+z-1]==B[0..z-1]的最大的z值（也就是B的自身匹配）。設(shè)目前next[0..lenB-1]與ex[0..i-1]均已求出，要用它們來(lái)求ex[i]的值。
設(shè)p為目前A串中匹配到的最遠(yuǎn)位置，k為讓其匹配到最遠(yuǎn)位置的值（或者說(shuō)，k是在0<=i0<i的所有i0值中，使i0+ex[i0]-1的值最大的一個(gè)，p為這個(gè)最大值，即k+ex[k]-1），顯然，p之后的所有位都是未知的，也就是目前還無(wú)法知道A[p+1..lenA-1]中的任何一位和B的任何一位是否相等。
根據(jù)ex的定義可得，A[k..p]==B[0..p-k]，因?yàn)閕>k，所以又有A[i..p]==B[i-k..p-k]，設(shè)L=next[i-k]，則根據(jù)next的定義有B[0..L-1]==B[i-k..i-k+L-1]。考慮i-k+L-1與p-k的關(guān)系：
（1）i-k+L-1<p-k，即i+L<=p。這時(shí)，由A[i..p]==B[i-k..p-k]可以得到A[i..i+L-1]==B[i-k..i-k+L-1]，又因?yàn)锽[0..L-1]==B[i-k..i-k+L-1]所以A[i..i+L-1]==B[0..L-1]，這就說(shuō)明ex[i]>=L。又由于next的定義可得，A[i+L]必然不等于B[L]（否則A[i..i+L]==B[0..L]，因?yàn)閕+L<=p，所以A[i..i+L]==B[i-k..i-k+L]，這樣B[0..L]==B[i-k..i-k+L]，故next[i-k]的值應(yīng)為L(zhǎng)+1或更大），這樣，
可以直接得到ex[i]=L！（2）i+k-L+1>=p-k，即i+L>p。這時(shí)，首先可以知道A[i..p]和B[0..p-i]是相等的（因?yàn)锳[i..p]==B[i-k..p-k]，而i+k-L+1>=p-k，由B[0..L-1]==B[i-k..i-k+L-1]可得B[0..p-i]==B[i-k..p-k]，即A[i..p]==B[0..p-i]），然后，對(duì)于A[p+1]和B[p-i+1]是否相等，目前是不知道的（因?yàn)榍懊嬉呀?jīng)說(shuō)過(guò)，p是目前A串中匹配到的最遠(yuǎn)位置，在p之后無(wú)法知道任何一位的匹配信息），因此，要從A[p+1]與B[p-i+1]開始往后繼續(xù)匹配（設(shè)j為目前B的匹配位置的下標(biāo)，一開始j=p-i+1，每次比較A[i+j]與B[j]是否相等，直到不相等或者越界為止，此時(shí)的j值就是ex[i]的值）。在這種情況下，p的值必然會(huì)得到延伸，因此更新k和p的值。
邊界：ex[0]的值需要預(yù)先求出，然后將初始的k設(shè)為0，p設(shè)為ex[0]-1。
對(duì)于求next數(shù)組，也是“自身匹配”，類似KMP的方法處理即可。唯一的不同點(diǎn)也在邊界上：可以直接知道next[0]=lenB，next[1]的值預(yù)先求出，然后初始k=1，p=ex[1]。
需要嚴(yán)重注意的是，在上述的情況（2）中，本該從A[p+1]與B[p-i+1]開始匹配，但是，若p+1<i，也就是p-i+1<0（這種情況是有可能發(fā)生的，當(dāng)ex[i-1]=0，且前面的ex值都沒(méi)有延伸到i及以后的時(shí)候）的話，需要將A、B的下標(biāo)都加1（因?yàn)榇藭r(shí)p必然等于i-2，如果A、B的下標(biāo)用兩個(gè)變量x、y控制的話，x和y都要加1）！！【核心代碼】
lenA = strlen(A); lenB = strlen(B);
next[0] = lenB; next[1] = lenB - 1;
re(i, lenB-1) if (B[i] != B[i + 1]) {next[1] = i; break;}
int j, k = 1, p, L;
re2(i, 2, lenB) {
p = k + next[k] - 1; L = next[i - k];
if (i + L <= p) next[i] = L; else {
j = p - i + 1;
if (j < 0) j = 0;
while (i + j < lenB && B[i + j] == B[j]) j++;
next[i] = j; k = i;
}
}
int minlen = lenA <= lenB ? lenA : lenB; ex[0] = minlen;
re(i, minlen) if (A[i] != B[i]) {ex[0] = i; break;}
k = 0;
re2(i, 1, lenA) {
p = k + ex[k] - 1; L = next[i - k];
if (i + L <= p) ex[i] = L; else {
j = p - i + 1;
if (j < 0) j = 0;
while (i + j < lenA && j < lenB && A[i + j] == B[j]) j++;
ex[i] = j; k = i;
}
}
【時(shí)間復(fù)雜度分析】
在KMP和擴(kuò)展KMP中，不管是A串還是B串，其匹配位置都是單調(diào)遞增的，故總時(shí)間復(fù)雜度是線性的，都為O(lenA + lenB)（只是擴(kuò)展KMP比KMP的常數(shù)更大一些）。
【應(yīng)用】
KMP和擴(kuò)展KMP在解決字符串問(wèn)題中有大用。很多看上去很猥瑣的字符串問(wèn)題，都可以歸結(jié)到這兩種算法之中。另外，這里的“字符串”可以延伸為一切類型的數(shù)組，而不僅僅是字符數(shù)組。