在數(shù)據(jù)結(jié)構(gòu)課上老師講了kmp算法非凌，但當(dāng)時并沒太懂，現(xiàn)在把思路重新理一遍荆针。
1.kmp算法簡介
KMP是三位大牛：D.E.Knuth敞嗡、J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的。
KMP算法其實就是一種改進(jìn)的字符串匹配算法航背，關(guān)鍵是利用匹配后失敗的信息喉悴，盡量減少模式串（W）與主串（T）的匹配次數(shù)以達(dá)到快速匹配的目的。具體實現(xiàn)就是實現(xiàn)一個next() 函數(shù)玖媚，函數(shù)本身包含了模式串的局部匹配信息箕肃。時間復(fù)雜度 O(m+n)。
如果考慮最笨的方法今魔，我們可以將T[0]和W[0]進(jìn)行匹配勺像，如果相同則匹配下一個字符障贸，直到出現(xiàn)不相同的情況，此時我們會丟棄前面的匹配信息吟宦，然后把T[1]跟W[0]匹配篮洁，循環(huán)進(jìn)行，直到主串結(jié)束殃姓，或者出現(xiàn)匹配成功的情況袁波。這種丟棄前面的匹配信息的方法，時間復(fù)雜度為O(mn)辰狡。
KMP算法利用已經(jīng)部分匹配這個有效信息锋叨，保持i指針（主串）不回溯，通過修改j指針宛篇，讓模式串盡量地移動到有效的位置，具體可見下面一個例子薄湿。
如果主串為：a b c a b c d h i j k
模式串為：a b c e
當(dāng)我們匹配到主串的第四個字符a時叫倍，可知a和e不相等，因此需要移向下一位豺瘤，但其實我們并不需要從模式串中的第一位重新開始比較吆倦，因為主串中的前三個字符已經(jīng)沒有未匹配的a了，不可能匹配成功坐求。
[站外圖片上傳中...(image-f5d3d1-1518266644982)]
2.next（）函數(shù)
因此蚕泽，最關(guān)鍵的是找到如何移動j指針。我們記當(dāng)匹配失敗時桥嗤，j要移動的下一個位置為k（即next[j]= k)须妻。記P為模式串。
很顯然泛领，存在這樣一個性質(zhì)：最前面的k個位置（對于模式串來說）和j之前的最后k個字符（主串）是一樣的荒吏。因此得到公式：
P[0 ~ k-1] == P[j-k ~ j-1]
當(dāng)P[k] == p[j]時
有P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]，即：P[0 ~ k] == P[j-k ~ j]渊鞋，因此可得
next[j+1] == k + 1 == next[j] + 1
當(dāng)P[k] != p[j]時
我們只能在0~k-1中去尋找最長后綴串了绰更，因此為
k = next[k]
使用C++ 實現(xiàn)next函數(shù)為
int* getNext(string p)
{
int* next = new int[p.length()];
next[0] = -1; //while the first char not match, i++,j++
int j = 0;
int k = -1;
while (j < (int)p.length() - 1)
{
if (k == -1 || p[j] == p[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
return next;
}
3.完整算法
int KMP(string T,string p)
{
int i=0;
int j=0;
int* next=getNext(T);
while (i < (int)T.length() && j < (int)p.length())
{
if (j == -1 || T[i] == p[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if (j == (int)p.length())
{
return i-j;
}
return -1;
}
