匹配
很簡(jiǎn)單，用next[x]表示前移數(shù)組。
// 偽代碼
while(!complete()) {
if(match(c[i], str[j]))
i++,j++;
else
i = next[i];
}
return j+1-len(c);
next[i]的生成
匹配過(guò)程事實(shí)上非常簡(jiǎn)單，難的是next[x]的生成。
思路：用兩個(gè)迭代器，遞歸思想。
記號(hào)：用c[x]表示待處理字符串，用next[x]表示前移數(shù)組。
樸素next生成算法
這樣求出來(lái)的next[x]有以下性質(zhì)：
-
c[0]=>c[next[x-1]]的字符串匹配c[x-1-next[x-1]]=>c[x-1]的字符串 -
next[x]是滿足以上條件的最大值
從這一表達(dá)式可以看出，next[x]從數(shù)學(xué)上難以直觀求解。
注：有人使用“前綴”“后綴”來(lái)表示1.條件，令人十分不習(xí)慣，還需要進(jìn)一步翻譯成數(shù)學(xué)語(yǔ)言，太不直接
使用兩個(gè)迭代器i,k其中i在前，k在后。每一次迭代的結(jié)果是求出next[i+1]。上一次迭代之后，顯然i=i+1，k應(yīng)當(dāng)滿足：
- 處于這樣一個(gè)位置，即“從
c[0]到c[k]的字符序列完全匹配從c[i-k]到c[i]的字符序列”。比如，"abab"k=2, i=4或者"aaaa"k=3,i=4。容易驗(yàn)證，空串(k=-1,i=0)滿足這個(gè)狀態(tài)。 - k是滿足條件1.的最大可能值。
滿足這一條件時(shí)，考慮next[i+1]，可見(jiàn)直接讓next[i+1]=k+1，我們便滿足了next[x]的兩條性質(zhì)。且慢！這里要使遞歸進(jìn)行下去，還要使末態(tài)滿足下面兩條性質(zhì)。怎么做呢？
若c[i+1]==c[k+1]是最皆大歡喜的事情。這時(shí)k=k+1自然滿足條件。次好的事情是k==-1，如果c[i+1]==c[0]不滿足，只要繼續(xù)讓k=-1就好了。不然的話怎么弄呢？需要減少匹配的字符數(shù)。本質(zhì)上，這又是一個(gè)c與自己的匹配！這么考慮：“從c[0]到c[k]的字符序列完全匹配從c[i-k]到c[i]的字符序列”，c[i+1]==c[k+1]不滿足。于是移動(dòng)c，從下一個(gè)可能的匹配位置開(kāi)始匹配，直到“從c[0]到c[k']的字符序列完全匹配從c[i+1-k']到c[i+1]的字符序列”.
// 循環(huán)內(nèi)部
next[i+1]=k+1;
if(c[k+1]==c[i+1])
k++;
else {
if(k==-1)
// 什么也不做
else {
k = k+1-KMP(c, c+i-k); // 偽代碼，被匹配者最大到c+i+1
}
}
i++;
// 上面?zhèn)未a事實(shí)上包括了特殊情況，自行驗(yàn)證一下！
// 循環(huán)內(nèi)部
next[i+1]=k+1;
k = k+1-KMP(c, c+i-k);
i++;
我們?cè)囍哑ヅ溥^(guò)程寫(xiě)開(kāi)。
next[i+1]=k+1;
m=0, n=0;
while(true) {
if(c[m]==c[i-k+n]) {
/* if(m>i) break; */ //不可能發(fā)生
if(n>k+1) break; // n==k+2
m++,n++;
}
else {
m=next[m];
if(m==-1) break;
}
}
// k=k+1-((k+2)-(m+1))
k=m;
i++;
這種寫(xiě)法未免過(guò)于復(fù)雜。事實(shí)上，第一趟匹配中，c[0=>k]其實(shí)都是匹配好的?？梢越璐撕?jiǎn)化代碼：
next[i+1]=k+1;
m=k+1, n=k+1;
while(m!=-1 && n<=k+1) {
if(c[m]==c[i-k+n])
m++,n++; // 事實(shí)上循環(huán)直接跳出了
else
m=next[m];
}
k=m;
i++;
我們發(fā)現(xiàn)變量n其實(shí)是多余的。
next[i+1]=k+1;
m = k+1;
while(m>=0 && c[m]!=c[i+1])
m=next[m]; // k=next[k+1]-1
k=m;
i++;
m也是多余的。把上面的代碼改寫(xiě)一下，成為如下簡(jiǎn)單形式：
while(k>=0 && c[k]!=c[i])
k=next[k];
i++,k++;
next[i]=k;
優(yōu)化的next生成算法
next數(shù)組滿足的條件為：
-
c[0]=>c[next[x-1]]的字符串匹配c[x-1-next[x-1]]=>c[x-1]的字符串 c[x]!=c[next[x]]-
next[x]是滿足以上條件的最大值
上面的算法腦抽了，要想匹配少，顯然k越小越好。比如，要匹配"abababac"，僅考慮前5位，next[5]應(yīng)該為3. 但第6位b不匹配，第4位b也不可能匹配。這就其實(shí)可以進(jìn)一步減小k的值，只需要加一個(gè)判斷：
while(k>=0 && c[k]!=c[i])
k=next[k];
i++,k++;
if(c[i]==c[k])
next[i]=next[k];
else
next[i]=k;
用數(shù)學(xué)歸納法可以證明，優(yōu)化的這一算法生成的next[x]滿足上面三點(diǎn)條件。
完整代碼(C語(yǔ)言)
// KMP
#define MAX_LEN 50
typedef struct
{
char c[MAX_LEN];
int n;
} SeqString, *pSeqString;
void makeNext(pSeqString p, int next[])
{
int i = 0, k = -1;
next[0] = -1;
while (i < p->n - 1)
{
while (k >= 0 && p->c[i] != p->c[k])
k = next[k];
i++;
k++;
// next[i] = k;
if (p->c[i] == p->c[k])
next[i] = next[k];
else
next[i] = k;
}
}
int pMatch(pSeqString t, pSeqString p, int next[])
{
int i = 0, j = 0;
while (i < p->n && j < t->n)
if (i == -1 || p->c[i] == t->c[j])
{
i++;
j++;
}
else
i = next[i];
if (i >= p->n)
return (j - p->n + 1);
else
return 0;
}
擴(kuò)展
KMP算法的匹配，思想和“狀態(tài)機(jī)”有一定的相似性。兩個(gè)迭代器對(duì)應(yīng)的字符進(jìn)行比較，失敗則改變一下“狀態(tài)”，改變的方式由next[x]數(shù)組定義。KMP算法的一種進(jìn)階形式是AC自動(dòng)機(jī)算法，可以處理更加復(fù)雜的多維匹配問(wèn)題。
