基本思想
設主串（下文中我們稱作T）為：a b a c a a b a c a b a c a b a a b b
模式串（下文中我們稱作W）為：a b a c a b
用暴力算法匹配字元串過程中，我們會把T[0] 跟 W[0] 匹配，如果相同則匹配下一個字元，直到出現不相同的情況，此時我們會丟棄前面的匹配信息，然後把T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配成功的情況。這種丟棄前面的匹配信息的方法，極大地降低了匹配效率。
而在KMP算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
比如，在簡單的一次匹配失敗後，我們會想將模式串儘量的右移和主串進行匹配。右移的距離在KMP算法中是如此計算的：在 已經匹配的模式串子串中，找出最長的相同的前綴和後綴，然後移動使它們重疊。
在第一次匹配過程中
T: a b a c a a b a c a b a c a b a a b b
W: a b a c a b
在T[5]與W[5]出現了不匹配，而T[0]~T[4]是匹配的，現在T[0]~T[4]就是上文中說的 已經匹配的模式串子串，現在移動找出 最長的相同的前綴和後綴並使他們重疊：
T: a b a c a a b a c a b a c a b a a b b
W: a b a c a b
然後在從上次匹配失敗的地方進行匹配，這樣就減少了匹配次數，增加了效率。
然而，如果每次都要計算 最長的相同的前綴反而會浪費時間，所以對於模式串來說，我們會提前計算出每個匹配失敗的位置應該移動的距離，花費的時間就成了常數時間。比如：
| j | 0 | 1 | 2 | 3 | 4 | 5 |
| W[j] | a | b | a | c | a | b |
| F(j) | 0 | 0 | 1 | 0 | 1 | 2 |
當W[j]與T[j]不匹配的時候，設定j = F(j-1).
文獻中，朱洪對KMP算法作了修改，他修改了KMP算法中的next函式，即求next函式時不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他記修改後的next函式為newnext。顯然在模式串字元重複高的情況下，朱洪的KMP算法比KMP算法更加有效。
以下給出朱洪的改進KMP算法和next函式和newnext函式的計算算法。
串匹配算法
輸入： 正文串T[1,n]和模式串W[1,m]
輸出： 匹配結果match[1,n]
next和newnext
輸入： 模式串W[1,m]
輸出： next[1,m+1]和newnext[1,m]
朱洪證明了算法1的時間複雜度為O(n），算法2的時間複雜度為O(m）。
更加簡潔的算法
下面是更加簡潔的算法：
計算過程
假設在執行正文中自位置 i 起“返前”的一段與模式的自右至左的匹配檢查中，一旦發現不匹配（不管在什麼位置），則去執行由W[m]與t[i]+d(x）起始的自右至左的匹配檢查，這裡x是字元t。它的效果相當於把模式向右滑過d(ti）一段距離。顯然，若ti不在模式中出現或僅僅在模式末端出現，則模式向右滑過的最大的一段距離m。圖1.1示出了執行BM算法時的各種情況。實線連線發現不匹配以後要進行比較的正文和模式中的字母，虛線連線BM算法在模式向右滑後正文和模式中應對齊的字母，星號表示正文中的一個字母。
圖1.1：執行BM算法時的各種情況
BM算法由算法1.3給出，函式d的算法由算法1.4給出。計算函式d的時耗顯然是Θ（m）。BM算法的最壞情況時耗是Θ（mn）。但由於在實用中這種情況極少出現，因此BM算法仍廣泛使用。
BM串匹配
輸入： 正文串W[1,m]和模式串T[1,n]
輸出： 匹配結果match[1,n]
d函式
因此有 h(xi+1）=((h(xi)-x·ord(ti））·d+ord(ti+m)mod q ，i=1,2，……，n-m
這裡x是一常數，x=dm-1mod q。這就是計算每一長度為m的字元段的散列函式值的遞推公式。RK串匹配算法由算法1.5給出。
RK串匹配
顯然，如果不計執行匹配檢查的時間，則RK算法的剩餘部分執行時間是Θ（m+n)。不過，如果計及執行匹配檢查的時間，則在理論上，RK算法需要時耗Θ（mn）。但是，我們總可設法取q適當大，使得mod函式在計算機中仍可執行而衝突（即不同的字元串具有相同的散列值）又極小可能發生，而使算法的實際執行時間只需Θ（m+n）。
BM算法
BM算法和KMP算法的差別是對模式串的掃描方式自左至右變成自右至左。另一個差別是考慮正文中可能出現的字元在模式中的位置。這樣做的好處是當正文中出現模式中沒有的字元時就可以將模式大幅度滑過正文。
BM算法的關鍵是根據給定的模式W[1,m]，，定義一個函式d: x->{1,2，…，m},這裡x∈∑。函式d給出了正文中可能出現的字元在模式中的位置。
最佳化
最佳化思路
KMP算法是可以被進一步最佳化的。
我們以一個例子來說明。譬如我們給的P字元串是“abcdaabcab”，經過KMP算法，應當得到“特徵向量”如下表所示：
| 下標i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| p(i) | a | b | c | d | a | a | b | c | a | b |
| next[i] | -1 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 3 | 1 |
但是，如果此時發現p(i) == p(k），那么應當將相應的next[i]的值更改為next[k]的值。經過最佳化後可以得到下面的表格：
| 下標i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| p(i) | a | b | c | d | a | a | b | c | a | b |
| next[i] | -1 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 3 | 1 |
| 最佳化的next[i] | -1 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 3 | 0 |
（1）next[0]= -1 意義：任何串的第一個字元的模式值規定為-1。
（2）next[j]= -1 意義：模式串T中下標為j的字元，如果與首字元相同，且j的前面的1—k個字元與開頭的1—k個字元不等（或者相等但T[k]==T[j]）（1≤k<j），如：T=”abCabCad” 則 next[6]=-1，因T[3]=T[6].
（3）next[j]=k 意義：模式串T中下標為j的字元，如果j的前面k個字元與開頭的k個字元相等，且T[j] != T[k] （1≤k<j）即T[0]T[1]T[2]......T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1]且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意義：除（1）（2）（3）的其他情況。
補充一個next[]生成代碼：
C++ 原始碼
KMP算法查找串S中含串P的個數count
Pascal 原始碼
kmp函式用於模式匹配，str_t是模式串，str_s是原串。返回模式串的位置，找不到則返回0。
