克努斯-莫里斯-普拉特演算法（KMP Algorithm）

「克努斯-莫里斯-普拉特演算法（Knuth–Morris–Pratt algorithm / KMP algorithm）」是一種字串搜尋演算法（string-searching algorithm），可用來在一長串文字中，尋找特定字串。

匹配陣列（PS Array）

用來比較一字串中的內容重複出現的程度；在比較兩字串時，若兩字串不相符，匹配陣列（PS Array）可協助將比較的字串往後移。

在生成「PS Array」時，會將一索引值對應的內容與前面的內容相較，重複出現的內容越長，則「PS Array」累加的數字越高，例如生成「棗子（jujube）」這個單字的「PS Array」時，結果為 001200，過程如下：

第一輪：n=0、i=1，預設索引值 0 處的「PS Array」值為 0：

第二輪：n=0、i=2：

第三輪：n=1、i=3：

第四輪：n=2、i=4：

第五輪：n=0、i=5：

為了要將該字串與其他字串配對比較，須將「PS Array」全部往右移動一個索引值，原本索引值為 0 對應的陣列值則先改成「?」，稍後將回頭說明這個「?」應該填什麼數字。

當「jujube」這個字串要拿去跟其他字串比較，若兩字串出現不同的內容，將「jujube」往右移動的格數，即為另一字串比較處的索引值減去「jujube」在「PS Array」中的數字。

「PS Array」功能演示：範例一

若將「jujube」與「jujuju」比較，則當「jujube」的第二個「j」對應到「jujuju」的第三個「j」時，兩者內容不同，則將「jujube」往右移動的格數就是「jujuju」的第三個「j」的索引值 4 減去「jujube」第二個「j」的「PS Array」值 2，一共要移動兩格：

移動後進行下一輪比較時，兩字串相對位置如下：

「PS Array」功能演示：範例二

現在將「jujube」與同義詞「jujuba」比較，則當「jujube」的最後一個字母「e」對到「jujuba」的最後一個字母「a」時，兩者才不相同，「jujube」要往右移動的格數相當於「jujuba」中「a」的索引值 5 扣除「jujube」的「e」對應「PS Array」的值 0，等於要一次移動五格。

移動後，兩字串相對位置如下：

由上述比較可以發現，有了「PS Array」輔助，字串右移的幅度變大，已經比較過、確定不會相同的部分都不會重複比較，比一格一格往右移快速許多。

「PS Array」第一個值

最後，讓我們來將「PS Array」字串中的問號填上正確數字。如果第一個字就不一樣，代表整個字串要往右移動一格，此時另一字串的索引值要扣掉多少，結果才會為 1 呢？

答案是 (-1)，實際運算過程如下：

最後可推得「jujube」的「PS Array」如下：

在任何的字串中，因為只要第一格內容相異就必會往右邊移動一格，因此「PS Array」的第一項必為 (-1)。

克努斯-莫里斯-普拉特演算法（KMP Algorithm）

在這個演算法中，共有下列幾個值：

1. String1：欲搜尋的範圍，可擴大至一篇文章、一頁網站等。
2. String2：欲尋找的字串。
3. 指標：「i」指向「String1」內容、「j」指向「String2」內容。
4. Counter：表示「String2」出現在「String1」的次數。

若兩字串指標的內容不同，就將「i」移動「i-PS[j]」格、「j」退回 0，相當於把整個「String2」往右移動「i-PS[j]」格後再開始比較。

現假設要在「take jujube jujas」中尋找「jujube」字串，KMP 演算法程圖示如下：

上述步驟中，「i」跟「j」對應到的內容都不一樣，因此只要將「String1」的「i」指標持續往右移動即可，也就是把「String2」一格一格往右移。

在下面的步驟中，「i」的內容開始與「String2」的「j」匹配，因此「j」指標也會往右移動，但「String2」本身留在原位，直到兩匹配資料內容不同、或比較完整個「String2」後發現該字串的內容完整出現在「String1」為止。

當「j」指標完整走過「String2」後，發現「String1」中有完全相同的內容，因此將「Counter」加上 1，代表在「String1」中找到一組「String2」。

一樣將「String2」的「j」指標所在處往右移動到對齊「String1」的「i」指標處。

接著重複一樣的比較流程：若無匹配內容則持續將「String2」隨著「i」往右移；若有匹配內容則讓「String2」留在原處與「String1」比較，直到兩字串內容不同、或又在「String1」中找到完整的「String2」為止。

「i」指標移到第 15 項時，發現與「j」指標內容不同，因此將「i」指標換到「i-PS[j]」處，索引值為 14。

「i」指標看似往前移動，實際上代表將「String2」第 0 項對到「String1」第 14 項進行比較，此時「i」與「j」兩指標內容不同，因此重複上述右移流程。

在上面的步驟中，「i」看似留在原地，其實代表「String2」又往右移動一格。

兩指標內容不同，因此持續將「i」指標往右移動。

當「i」指標超出「String1」長度時，跳出迴圈，比較停止。

最終的「Counter」為 1，代表在「String1」中，找到一個「String2」字串。