在計算機科學中，字符串匹配是一個常見的問題。給定一個文本串和一個模式串，我們需要在文本串中找到所有與模式串匹配的位置。傳統的字符串匹配算法如暴力匹配（Brute Force）方法在最壞情況下的時間復雜度為O(m*n)，其中m和n分別是文本串（長的字符串）和模式串（短的字符串）的長度，kmp算法是一種高效的字符串匹配算法。

廢話不多說我們直接介紹重點，帶你理解kmp算法

1. kmp 算法原理?

為什么暴力匹配這么慢？

我們發現當每次匹配失敗后，bf算法都會讓 文本串（長的字符串）后退到匹配的第一個字符的下一個字符，讓模式串（短的字符串）后退到第一個字符，重新開始匹配，例如：

0 1 2 3 4 5 6 7 8 9 10
a b c a b a b c a b d
a b c a b d
0 1 2 3 4 5
當我們使用bf算法時，在 5 下標位置匹配失敗時，會讓 文本串 后退到 1 下標 ，讓模式串后退到 0 下標，重新開始匹配，但其實我們發現：文本串的 1 下標和 模式串的 0 下標其實并不匹配，其實大可跳過，文本串的 1 下標，如果重新匹配，我們發現，只有從文本串的 3 位置開始匹配才可能成功，kmp算法對于bf算法的優化就是在于，跳過了那些一定匹配不上的位置。

?kmp的算法核心在于，讓文本串不后退：

如上述例子，我們在5位置匹配失敗了，此處不讓文本串后退，只讓 模式串 后退，我們發現，文本串，的 3 4?下標是和模式串的 0 1 下標匹配的，所以我們可以讓，讓模式串后退到 2?下標位置，與 文本串 5 下標位置 進行比較：

0 1 2 3 4 5 6 7 8 9 10
a b c a b a b c a b d?
? ? ? ? ?a b c a b d
? ? ? ? ?0 1 2 3 4 5

即相當于，我們跳過了用 模式串 與 1 位置， 和 2 位置 的比較，因為這兩個位置匹配一定是失敗的，也跳過了 ，模式串 的 0 1 下標和，文本串的 3 4 下標的比較，因為我們知道一定是成功的，所以直接從模式串的 3 位置與文本串的 5 位置開始匹配

我們要如何知道 模式串 回退的位置？靠眼睛看肯定是不行的

如果上面的內容沒有看懂，沒關系，請重點理解下面的內容：

2. 最長前綴后綴

在模式串中，如果一個子串的前綴和后綴相同，則稱該子串為前綴后綴。例如，模式串"a b c a b "的前綴有"a"、"ab"、"abc"、"abca"、"abca"，后綴有"b"、"ab"、"cab"、"bcab"、"abca"。?
那么"abcab"的最長前綴后綴不就是 "ab"嗎。

注意：最長前綴后綴不能是這個字串本身

練習一下：
"abcdbcabcd"的最長前后綴是？
沒錯，是 "abcd"。現在你已經會求最長前后綴了，現在我們可以解決，模式串回退的位置的問題了，這是最關鍵的一步。
以剛才的例子來說：

0 1 2 3 4 5 6 7 8 9 10
a b c a b a b c a b d
a b c a b d
0 1 2 3 4 5
現在我們發現了不匹配的地方，根據kmp算法，我們只回退模式串，要知道回退的位置，我們剛才的最長前綴后綴就有用處了。我們發現：前面綠色的代碼匹配成功的字串。
我們現在把這兩個字串的最長前綴后綴標出：

0 1 2 3 4 5 6 7 8 9 10
a b c a b a b c a b d
a b c a b d
0 1 2 3 4 5

現在你發現了什么。
沒錯，模式串中匹配成功的字串的 0 1 下標?和 3 4 下標互為最長前綴后綴，即 0 1 下標 的字符與 3 4 下標的字符相等，即模式串的的0 1 下標與 文本串中的 3 4 下標 相等，所以我們移動模式串，讓模式串已經匹配成功的字串的 前綴 與 文本串中的后綴對應：

0 1 2 3 4 5 6 7 8 9 10
a b c a b a b c a b d
? ? ? ? ?a b c a b d
? ? ? ? ?0 1 2 3 4 5
于是我們得出，模式串匹配失敗后的回退的位置 為 最長前后綴的 前綴 的后一個位置，也就是前綴/后綴的長度當前例子為 2?

如果理解了這一步，kmp 的關鍵你就已經掌握了。
接下來就是一個重復的過程了，模式串中每一個字符的前面的字串都有最長前綴后綴，而且最長相等前后綴的長度是我們移位的關鍵，所以我們用一個next數組記錄下每個字符前面的字串的最長前綴后綴的長度，即在該字符匹配失敗后模式串回退的位置。
例如：a b c a b d 的next數組為：
下標：? ? ? ? ? 0 1 2 3 4 5?
模式串：? ?? ? a b c a b d
next數組：? ?-1 0 0 0 1 2
注意：在第一個位置 為 -1 做特殊處理，下面會詳細講解。最長前后綴為空字符串即長度為0。

下面做一個練習：
abcababcabca的next數組為？
?

答案：

-1 0 0 0 1 2 1 2 3 4 5 3

3. 計算next 數組

?將next數組用代碼計算出來：

我們發現，next 的值一定是序數遞增的，不會由 0 直接到2，只能先到1 再到2。

舉個例子：
?0 1 2 3 4 5
?a b c a b d
-1 0 0 0?1 2

5 位置前的字串 最長前綴后綴為 a b 長度為2，那 4 前面的字串的最長前綴后綴一定為 a?
如果4 前面 的最長前綴后綴為 0 即 0 位置的字符，與 3 位置的字符沒有匹配上，? 5 前面的字串的 最長前綴后綴 長度要為2 的話只能是 0 1小標和3 4 下標，所以0 3下標必須是匹配的 長度才可能為2。

那么，我們求 next數組，是不是就可以只判斷當前的前一個字符是不是和他的最長前綴后綴的長度的對應位置的字符是否相等，如果相等，則當前的next值即為前一個值+1.

舉個例子：

?0? 1? 2? 3? 4? 5? 6? 7? 8? 9?10 11
?a??b? c? a? b? a? b? c? a? b? ?c? ?a
-1? 0? 0? 0

現在要求4下標的next值，我們判斷 4 下標的前一個字符 即 3下標的 a?是否和 它的?最長前綴后綴的長度 即對應的next值 即 0 位置的元素 即 a 是否相等 ，顯然 a 與 a 相等，所以 4 下標的值應為?
0 + 1 = 1
?0? 1? 2? 3? 4? 5? 6? 7? 8? 9?10 11
?a??b? c? a? b? a? b? c? a? b? ?c? ?a
-1? 0? 0? 0? 1? ??
同理，5下標 只需判斷 4 下標 下的字符 是否等于 1 下標的字符，顯然相等，所以 5 下標下的值應該為 1 + 1 = 2。

?0? 1? 2? 3? 4? 5? 6? 7? 8? 9?10 11
?a??b? c? a? b? a? b? c? a? b? ?c? ?a
-1? 0? 0? 0? 1? 2??

那如果比較的字符不相等呢？

?0? 1? 2? 3? 4? 5? 6? 7? 8? 9?10 11
?a??b? c? a? b? a? b? c? a? b? ?c? ?a
-1? 0? 0? 0? 1? 2??1? 2? 3? 4? ?5? ??
如現在求11下標的next值，我們比較 10?下標的 字符和 5?下標的字符 發現并不相等。
注意！！此時我們繼續 判斷 5?下標下的 next 的值 即 2?對應位置的字符是否和 10?下標下的字符相等，顯然 c?== c?,所以 10?下標下的 next 值即為 2?+ 1 = 3.

以下為證明過程，理解不了直接記下結論即可

解釋：因為我們嘗試在 11?的前面找比 5?更長的最長前后綴，顯然 匹配失敗了，代表找不到，所以我們，繼續向前，找“最長前后綴的前后綴的長度”，即在 abcab中找最長前綴后綴，即 5 下標下的next 值 2，由于 10 下標前的 最長前綴后綴的長度是知道的 ，即 5 ,說明 0 到 4 下標與 5 到 9 下標是匹配的，先找到 0 到 4 下標字串的最長前綴后綴 的長度為 ，2 那說明 0 1 下標 與 2 4 下標匹配，又因為 0 4 下標與 5 9 下標匹配 ，所以 ，0 1 下標 與 8 9 下標匹配，所以我們直接判斷，2 下標與10 下標下的字符是否相等，相等則該下標對應的next 值應為 2 + 1 = 3. 如果不相等 則 繼續 用 2 對應的 next 值往下找直到 為 -1 時做特殊處理

代碼實現：

c語言版：

int* getNext(char* s, int len)
{//申請一塊內存用于返回next數組int* next = (int*)malloc(4 * len);next[0] = -1; //處理特殊值,以便代碼實現next[1] = 0; //第二個字符匹配失敗一定是回到 0 位置開始比較int k = 0; // 代表前一個下標的 next 值，我們從2開始，所以k初始為next[1] = 0int i = 2;while (i < len){//判斷當前位置前一個字符是否等于 k 位置的 字符if (s[i - 1] == s[k]){//相等則當前位置的next值為 k + 1next[i] = k + 1;//讓 i++i++;//讓k的值更新k++;}else{//匹配失敗，讓當前字符與，next[k] 下標下的字符進行比較//我們這里直接更新k的值，在下一次循環比較,注意不需要 i++k = next[k];}}return next;
}

注意如果一直匹配失敗會導致 k 的值 為 -1 導致 上面 數組越界
所以我們在上方的if中做特殊處理

int* getNext(char* s, int len)
{int* next = (int*)malloc(4 * len);next[0] = -1; //處理特殊值,以便代碼實現next[1] = 0; //第二個字符匹配失敗一定是回到 0 位置開始比較int k = 0; // 代表前一個下標的 next 值，我們從2開始，所以k初始為next[1] = 0int i = 2;while (i < len){//判斷當前位置前一個字符是否等于 k 位置的 字符，注意處理 k == -1if (k == -1 || s[i - 1] == s[k]){//相等則當前位置的next值為 k + 1next[i] = k + 1;//讓 i++ 進入下次循環繼續獲取next數組i++;//讓k的值更新k++;}else{//匹配失敗，讓當前字符與，next[k] 下標下的字符進行比較//我們這里直接更新k的值，在下一次循環比較,注意不需要 i++k = next[k];}}return next;
}

我們讓k等于-1的時候也進入if內部，當k等于-1說明，當前i位置的字符前面最長前綴后綴的長度為0，此時我們給 next[i] 賦的值為 -1 + 1 = 0，所以這就是我們為什么要把next[0] 設置為 -1?

現在我們的 kmp 算法以及完成大半了，只需再寫一個 函數用來比較兩個字符串，在匹配失敗的時候用next數組找到 模式串回退的位置，然后繼續比較即可。

代碼實現：

int KMP(char* s1, char* s2, int len1, int len2)
{int* next = getNext(s2, len2);int i = 0;int j = 0;while (i < len1 && j < len2){//注意處理j為-1的情況if (j == -1 || s1[i] == s2[j]) {i++;j++;}else{j = next[j];}}if (j == len2){//j == len2 說明匹配成功了，返回s1中匹配成功時，匹配的第一個字符的位置return i - j;}//匹配失敗返回-1return -1;
}

至此我們的 kmp 算法就完成了，如果覺得對你有幫助的話，請給一個免費的贊，有什么問題也可以在下方討論。

Java代碼：
?

    //求next數組public static int[] getNext(String s) {int n = s.length();int[] next = new int[n];next[0] = -1;//處理特殊值,以便代碼實現int i = 2;//第二個字符匹配失敗一定是回到 0 位置開始比較所以直接從 2 位置開始int k = 0; // 代表前一個下標的 next 值，我們從2開始，所以k初始為next[1] = 0while (i < n) {//判斷當前位置前一個字符是否等于 k 位置的 字符，注意處理 k == -1if(k == -1 || s.charAt(i-1) == s.charAt(k)) {//相等則當前位置的next值為 k + 1next[i] = k + 1;//讓k的值更新k++;//讓 i++ 進入下次循環繼續獲取next數組i++;}else {//匹配失敗，讓當前字符與，next[k] 下標下的字符進行比較//我們這里直接更新k的值，在下一次循環比較,注意不需要 i++k = next[k];}}return next;}public static int KMP(String s1, String s2) {int n = s1.length();int m = s2.length();int i = 0;int j = 0;int[] next = getNext(s2);while(i < n && j < m) {//注意處理 j == -1if(j == -1 || s1.charAt(i) == s2.charAt(j)) {i++;j++;}else{j = next[j];}}if(j == m) {return i - j;}return -1;}