角色：
甲：abbaabbaaba
乙：abbaaba
乙對甲說：「幫忙找一下我在你的哪個位置。」
甲從頭開始與乙一一比較，發現第 7 個字元不比對。
要是在往常，甲會回退到自己的第 2 個字元，乙則回退到自己的開頭，然後兩人開始重新比較。[1]這樣的事情在字元串王國中每天都在上演：不比對，回退，不比對，回退，……
但總有一些妖豔字元串要花出自己不少的時間。
上了年紀的甲想做出一些改變。于是甲把乙叫走了：「你先一邊玩去，我自己研究下。」
甲給自己定了個小目标：發生不比對，自己不回退。
甲發現，若要成功與乙比對，必須要比對 7 個字元。也就是說，就算自己回退了，在後續的比對流程中，肯定還要比對自己的第 7 個字元。
當在甲的某個字元 c 上發生不比對時，甲即使回退，最終還是會重新比對到字元 c 上。
那幹脆不回退，豈不美哉！
甲不回退，乙必須回退地盡可能少，并且乙回退位置的前面那段已經和甲比對，這樣甲才能不用回退。
如何找到乙回退的位置？
「不比對發生時，前面比對的那一小段 abbaab 于我倆是相同的」，甲想，「這樣的話，用 abbaab 的頭部去比對 abbaab 的尾部，最長的那段就是答案。」
具體來說，
abbaab 的頭部有 a, ab, abb, abba, abbaa（不包含最後一個字元。下文稱之為「字首」）
abbaab 的尾部有 b, ab, aab, baab, bbaab（不包含第一個字元。下文稱之為「字尾」）
這樣最長比對是 ab，乙回退到第三個字元和甲繼續比對。 「要計算的内容隻和乙有關」，甲想，「那就假設乙在所有位置上都發生了不比對，乙在和我比對之前把所有位置的最長比對都算出來（算個長度就行），生成一張表，之後我倆發生不比對時直接查這張表就行。」
據此，甲總結出了一條甲方規則：
所有要與甲比對的字元串，必須先自身比對：對每個子字元串 [0...i]，算出其「相比對的字首與字尾中，最長的字元串的長度」。
甲把乙叫了回來，告訴他新出爐的甲方規則。
「小 case，我對自己還不了解嗎」，乙眨了一下眼睛，「那我回退到第三個字元和你繼續比對就行了」。
有些算法，适合從它産生的動機，如何設計與解決問題這樣正向地去介紹。但KMP算法真的不适合這樣去學。最好的辦法是先搞清楚它所用的資料結構是什麼，再搞清楚怎麼用，最後為什麼的問題就會有恍然大悟的感覺。我試着從這個思路再介紹一下。大家隻需要記住一點，PMT是什麼東西。然後自己臨時推這個算法也是能推出來的，完全不需要死記硬背。KMP算法的核心，是一個被稱為部分比對表(Partial Match Table)的數組。我覺得了解KMP的最大障礙就是很多人在看了很多關于KMP的文章之後，仍然搞不懂PMT中的值代表了什麼意思。這裡我們抛開所有的枝枝蔓蔓，先來解釋一下這個資料到底是什麼。對于字元串“abababca”，它的PMT如下表所示：
就像例子中所示的，如果待比對的模式字元串有8個字元，那麼PMT就會有8個值。
我先解釋一下字元串的字首和字尾。如果字元串A和B，存在A=BS，其中S是任意的非空字元串，那就稱B為A的字首。例如，”Harry”的字首包括{”H”, ”Ha”, ”Har”, ”Harr”}，我們把所有字首組成的集合，稱為字元串的字首集合。同樣可以定義字尾A=SB， 其中S是任意的非空字元串，那就稱B為A的字尾，例如，”Potter”的字尾包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然後把所有字尾組成的集合，稱為字元串的字尾集合。要注意的是，字元串本身并不是自己的字尾。
有了這個定義，就可以說明PMT中的值的意義了。PMT中的值是字元串的字首集合與字尾集合的交集中最長元素的長度。例如，對于”aba”，它的字首集合為{”a”, ”ab”}，字尾 集合為{”ba”, ”a”}。兩個集合的交集為{”a”}，那麼長度最長的元素就是字元串”a”了，長 度為1，是以對于”aba”而言，它在PMT表中對應的值就是1。再比如，對于字元串”ababa”，它的字首集合為{”a”, ”ab”, ”aba”, ”abab”}，它的字尾集合為{”baba”, ”aba”, ”ba”, ”a”}， 兩個集合的交集為{”a”, ”aba”}，其中最長的元素為”aba”，長度為3。
好了，解釋清楚這個表是什麼之後，我們再來看如何使用這個表來加速字元串的查找，以及這樣用的道理是什麼。如圖 1.12 所示，要在主字元串"ababababca"中查找模式字元串"abababca"。如果在 j 處字元不比對，那麼由于前邊所說的模式字元串 PMT 的性質，主字元串中 i 指針之前的 PMT[j −1] 位就一定與模式字元串的第 0 位至第 PMT[j−1] 位是相同的。這是因為主字元串在 i 位失配，也就意味着主字元串從 i−j 到 i 這一段是與模式字元串的 0 到 j 這一段是完全相同的。而我們上面也解釋了，模式字元串從 0 到 j−1 ，在這個例子中就是”ababab”，其字首集合與字尾集合的交集的最長元素為”abab”， 長度為4。是以就可以斷言，主字元串中i指針之前的 4 位一定與模式字元串的第0位至第 4 位是相同的，即長度為 4 的字尾與字首相同。這樣一來，我們就可以将這些字元段的比較省略掉。具體的做法是，保持i指針不動，然後将j指針指向模式字元串的PMT[j −1]位即可。
簡言之，以圖中的例子來說，在 i 處失配，那麼主字元串和模式字元串的前邊6位就是相同的。又因為模式字元串的前6位，它的前4位字首和後4位字尾是相同的，是以我們推知主字元串i之前的4位和模式字元串開頭的4位是相同的。就是圖中的灰色部分。那這部分就不用再比較了。
有了上面的思路，我們就可以使用PMT加速字元串的查找了。我們看到如果是在 j 位 失配，那麼影響 j 指針回溯的位置的其實是第 j −1 位的 PMT 值，是以為了程式設計的友善， 我們不直接使用PMT數組，而是将PMT數組向後偏移一位。我們把新得到的這個數組稱為next數組。下面給出根據next數組進行字元串比對加速的字元串比對程式。其中要注意的一個技巧是，在把PMT進行向右偏移時，第0位的值，我們将其設成了-1，這隻是為了程式設計的友善，并沒有其他的意義。在本節的例子中，next數組如下表所示。
1 // 傳回值為首次比對的串的第一個字元的下标
2 /*
3 不能寫 while( i < t.length() && j < p.length() )，
4 因為當j = -1時，因為p.length()是無符号整數，則-1 > p.length(),
5 這樣就産生了錯誤
6 是以要事先用有符号整數儲存 t.length()和p.length()的值
7 */
8 int kmp(string t, string p)
9 {
10 int i = 0, j = 0;
11
12 int tlen = t.length();
13 int plen = p.length();
14 while (i < tlen && j < plen)
15 {
16 if (j == -1 || t[i] == p[j])
17 {
18 ++i;
19 ++j;
20 }
21 else
22 {
23 j = nxt[j];
24 }
25 }
26
27 if (j == plen)
28 return i - j;
29 else
30 return -1;
31 } 好了，講到這裡，其實KMP算法的主體就已經講解完了。你會發現，其實KMP算法的動機是很簡單的，解決的方案也很簡單。遠沒有很多教材和算法書裡所講的那麼亂七八糟，隻要搞明白了PMT的意義，其實整個算法都迎刃而解
現在，我們再看一下如何程式設計快速求得next數組。其實，求next數組的過程完全可以看成字元串比對的過程，即以模式字元串為主字元串，以模式字元串的字首為目标字元串，一旦字元串比對成功，那麼目前的next值就是比對成功的字元串的長度
具體來說，就是從模式字元串的第一位(注意，不包括第0位)開始對自身進行比對運算。 在任一位置，能比對的最長長度就是目前位置的next值。如下圖所示。
求next數組值的程式如下所示：
1 int nxt[1010];
2
3 // 已經有庫函數叫做next，是以next數組的命名不能再叫做next，否則會報next不明确的錯誤，這裡改為nxt
4 void getNext(string p, int nxt[])
5 {
6 nxt[0] = -1;
7 int i = 0, j = -1;
8
9 int plen = p.length();
10 while (i < plen)
11 {
12 if (j == -1 || p[i] == p[j])
13 {
14 ++i;
15 ++j;
16 nxt[i] = j; // nxt[1]恒等于0
17 }
18 else
19 {
20 j = nxt[j];
21 }
22 }
23 } 複雜度估計：
假設原串長度為n, 比對串長度為m。我們可以看到，比對串每次往前移動，都是一大段一大段移動，假設比對串裡不存在重複的字首和字尾，即next的值都是-1，那麼每次移動其實就是一整個比對串往前移動m個距離。然後重新一一比較，這樣就比較m次，概括為，移動m距離，比較m次，移到末尾，就是比較n次，O(n)複雜度。 假設比對串裡存在重複的字首和字尾，我們移動的距離相對小了點，但是比較的次數也小了，整體代價也是O(n)。是以複雜度是一個線性的複雜度O(n)。同理，求next數組的複雜度為O(m)，總體就為O(m+n)。