KMP演算法的核心，在於如何計算出《部分匹配表》（Partial Match Table）；下文中我們簡稱為PMT；如果理解了這個匹配表中的每一個值代表了什麼，那就能理解KMP演算法的實現原理了；

在大多數示例中，這個PMT會被稱之為next的一個數組；

對於字串‘ABCDABD’，它的PMT值如下表示：

要明白這裡的值代表什麼，需要先理解兩個概念：“字首”和“字尾”。 “字首”指除了最後一個字元以外，一個字串的全部頭部組合；“字尾”指除了第一個字元以外，一個字串的全部尾部組合。下面列出了hello的全部字首組合和world的全部字尾組合；

Hello

=

［

‘H’

，

‘He’

，

‘Hel’

，

‘Hell’

］；World

=

［

‘orld’

，

‘rld’

，

‘ld’

，d］

PMT就是"字首"和"字尾"的最長的共有元素的長度

。以“ABCDABD”為例：

// －“A”的字首和字尾都為空集，共有元素的長度為0；

// －“AB”的字首為［A］，字尾為［B］，共有元素的長度為0；

// －“ABC”的字首為［A， AB］，字尾為［BC， C］，共有元素的長度0；

// －“ABCD”的字首為［A， AB， ABC］，字尾為［BCD， CD， D］，共有元素的長度為0；

// －“ABCDA”的字首為［A， AB， ABC， ABCD］，字尾為［BCDA， CDA， DA， A］，共有元素為“A”，長度為1；

// －“ABCDAB”的字首為［A， AB， ABC， ABCD， ABCDA］，字尾為［BCDAB， CDAB， DAB， AB， B］，共有元素為“AB”，長度為2；

// －“ABCDABD”的字首為［A， AB， ABC， ABCD， ABCDA， ABCDAB］，字尾為［BCDABD， CDABD， DABD， ABD， BD， D］，共有元素的長度為0。

更簡單的理解方式，PMT的值就代表當前字串的字首和字尾重合的地方，如‘ABA’中，前面第一個A和後面第一個A是相同的，相同的字串A長度是1，則PMT值為1；如‘ABCDAB’，前面AB和後面AB是相同的，值PMT值為2（AB的長度）；

好了，解釋清楚這個表是什麼之後，我們來看一下原理是什麼；

如圖 1。12 所示，要在主字串“ababababca”中查詢模式字串“abababca”。如果在 j 處字元不匹配，那麼由於前邊所說的模式字串 PMT 的性質，主字串中 i 指標之前的 PMT［j 1］ 位就一定與模式字串的第 0 位至第 PMT［j1］ 位是相同的。這是因為主字串在 i 位失配，也就意味著主字串從 ij 到 i 這一段是與模式字串的 0 到 j 這一段是完全相同的。而我們上面也解釋了，模式字串從 0 到 j1 ，在這個例子中就是”ababab”，其字首集合與字尾集合的交集的最長元素為”abab”， 長度為4。所以就可以斷言，主字串中i指標之前的 4 位一定與模式字串的第0位至第 4 位是相同的，即長度為 4 的字尾與字首相同。這樣一來，我們就可以將這些字元段的比較省略掉。具體的做法是，保持i指標不動，然後將j指標指向模式字串的PMT［j 1］位即可。

簡言之，以圖中的例子來說，在 i 處失配，那麼主字串和模式字串的前邊6位就是相同的。又因為模式字串的前6位，它的前4位字首和後4位字尾是相同的，所以我們推知主字串i之前的4位和模式字串開頭的4位是相同的。就是圖中的灰色部分。那這部分就不用再比較了。

程式實現如下：

function KMP（m： string， n： string） {

//next陣列即是PMT值 後面介紹如何根據模式字串計算PMT值；

const next = getNext（n）；

let j = 0；

for （let i = 0； i < m。length； ） {

if （m［i］ === m［j］） {

i++；

j++；

} else {

// 當沒有匹配到的時候 透過PMT值來移動模式字串的匹配位置

j = next［j-1］；

}

// 相等代表已經匹配成功了，返回字串的起始位置；

if （j === n。length） return i - j；

}

// 沒有匹配上

return -1；

}

到這裡，KMP演算法的主體思路就講完了，我們再回頭來看看PMT值也就是next陣列是如何計算出來的；

具體來說，就是從模式字串的第一位（注意，不包括第0位）開始對自身進行匹配運算。 在任一位置，能匹配的最長長度就是當前位置的next值。如下圖所示。

求next陣列值的程式如下所示：

function getNext（n） {

let j = 0；

let next = ［0］；

for （let i = 1； i < n。length；） {

if （n［i］ === n［j］） {

// j+1是因為遍歷的時候從0開始的，而記值的時候是從1開始的

// 如aba去匹配a 值應該是1 而這時候的j是0；

next［i］ = j+1；

j++；

i++；

} else if（j===0）{

next［i］ = 0；

i++；

} else {

j = next［j］；

}

}

return next；

}

至此，KMP演算法的實現就完成了；