目的
- 已知字符串 S 和 T，查找 T 在 S 中的位置。
暴力匹配法
-
1-1、從下標(biāo) 0 位置開(kāi)始匹配，S[0]-->T[0]、S[1]-->T[1]、S[2]-->T[2]
KMP_1.jpeg -
1-2、當(dāng) S[i]-->T[j] 失配時(shí)，T 相對(duì)于 S 向右移動(dòng)一位再按照步驟1開(kāi)始匹配，S[1]-->T[0]...
KMP_2_1.jpeg 1-3、依此反復(fù)，直到匹配成功或者失敗...
我們注意到，既然在1-1中已經(jīng)知道了 S[1] == T[1]，而通過(guò) T 自身就可以知道 T[0] != T[1]，因此即使不進(jìn)行步驟1-2中 S[1]-->T[0] 的比較我們也知道 S[1] != T[0]。因此這樣顯然做了很多不必要的操作。
KMP 匹配推導(dǎo)
-
2-1、圖1中，匹配到 S[2]-->T[2] 時(shí)失配，說(shuō)明 S[0] == T[0]，且 S[1] == T[1]，即 S[0]...S[i] == T[0]...T[j]。假設(shè)有一個(gè)串 X 與 T[0]...T[j] 不匹配，那么這個(gè)串自然也與 S[0]...S[i] 不匹配。如圖3所示。
KMP_3.jpeg -
2-2、回頭看步驟1-2，這里用 T[0]（'A'）與 S[1]（'B'）比較，其實(shí)可看做 T[0] 與 T[1] 比較，如果 T[0] 與 T[1] 不匹配，依據(jù) 2-1 的推理，那么需要一個(gè)已經(jīng)匹配到的子串 T[0]...T[j]（步驟1-1中的j值為1）的前綴和后綴進(jìn)行比較的過(guò)程（T[0]...T[j-1]與T[1]...T[j]）。
KMP_4.jpeg 2-3、"前綴"指除了最后一個(gè)字符以外，一個(gè)字符串的全部頭部組合；"后綴"指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合。
2-4、圖4中的“前綴”有：0，01，012
2-5、圖4中的“后綴”有：3，23，123
-
2-6、如果“前綴”和“后綴”中沒(méi)有匹配的，則步驟1-2的“向右移動(dòng)一位”變成了向右移動(dòng)：
KMP_5.jpeg 2-7、步驟1-1中已經(jīng)匹配了的長(zhǎng)度為2，前后綴匹配最大值為0（前綴只有'A'，后綴只有'B'）。因此步驟1-2可以直接將 T 向右移動(dòng) 2 位進(jìn)行匹配。
2-8、計(jì)算 T 的子串（T[0]、T[0]...T[1]、~、T[0]...T[strlen(T)]）每一個(gè)的最大匹配值存儲(chǔ)到數(shù)組 next 中。
-
2-9、整個(gè)匹配過(guò)程就可以寫(xiě)作：從頭開(kāi)始匹配、遇到失配的字符就到 next 數(shù)組獲取當(dāng)前 T 的下標(biāo)對(duì)應(yīng)的值 k、根據(jù) k 值決定 T 向后移動(dòng)多少位然后開(kāi)始新一輪的匹配...，所以圖2-1可修改為圖2-2
KMP_2_2.jpeg
next 數(shù)組
3-1、定義用 k 表示某一子串的前后綴最大匹配值，next 數(shù)組依次存放 k 值。
3-2、任何一個(gè)字符串下標(biāo)為0時(shí)都沒(méi)有“前綴”和“后綴”，因此所有 next[0] = 0（為了不同的算法計(jì)算方便也有取為 -1 的）
-
3-3、假設(shè)我們知道了 next[j-1] 的值為 k，可以推斷出 T[0]...T[k-1] == T[j-k]...T[j-1]，接下來(lái)看 T[k] 和 T[j] 是否相等。
KMP_6.jpeg -
3-4、從圖6可以看出，如果 T[k] == T[j]，next[j] = next[j-1] + 1。如果 T[k] != T[j] 呢？為了更加直觀，我們把 T[0]...T[K]移到 T[j-k]...T[j] 的下方：
KMP_7.jpeg -
3-5、這樣確實(shí)可以達(dá)到目的，但是這種方式有沒(méi)有似曾相識(shí)？沒(méi)錯(cuò)！這不就是跟上面一樣的流程嘛，只是在子串中找子串的子串然后進(jìn)行匹配。
KMP_8.jpeg 3-6、我們知道 k 一定比 j 小，也比 j-1 小，既然 next[j-1] 是已知的，那么 next[k] 也一定已經(jīng)確認(rèn)過(guò)了。而我們又可以很輕易地推導(dǎo)出圖中圈出的三個(gè)小串是相互匹配的（這三個(gè)小串的長(zhǎng)度為 next[k]）。
3-7、因此我們這時(shí)候可以用 T[next[k]+1] 去和 T[j] 比較，如果相等，則 T[j] = next[k] + 1。如果不相等，則遞歸執(zhí)行 3-6、3-4，直到找到 T[j] 相匹配的字符或者直到子串長(zhǎng)度為0。
