前言
刷到字符串匹配的力扣題了【28. 實現(xiàn) strStr() 】，這題簡單吧用庫函數(shù)做就可以，說難吧，就得引出大名鼎鼎的線性匹配算法——KMP。

KMP

算法背景與原理

KMP（Knuth-Morris-Pratt）算法是一種高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt等人在1977年提出。該算法的核心思想是避免在字符串匹配過程中不必要的回溯，從而提高匹配效率。

在傳統(tǒng)的字符串匹配算法中，如Brute Force方法，一旦發(fā)現(xiàn)不匹配，模式串會回溯到下一個起始位置重新開始匹配。這種方法在最壞情況下的時間復雜度為O(nm)，其中n是主串長度，m是模式串長度。而KMP算法通過預處理模式串，構造一個部分匹配表（也稱為next數(shù)組），在發(fā)生不匹配時，可以跳過已經(jīng)確認不會匹配的部分，從而提高匹配效率。

核心思想:由傳統(tǒng)雙層循環(huán)遍歷入手優(yōu)化時間復雜度，優(yōu)化的手段是借助前綴表保證外層索引單向移動。

算法優(yōu)勢

KMP算法的主要優(yōu)勢在于其時間復雜度為O(n+m)，相比傳統(tǒng)的Brute Force方法，KMP算法在最壞情況下也能保持較高的效率。這是因為KMP算法利用了已經(jīng)匹配的信息來避免不必要的重復比較。具體來說，KMP算法的優(yōu)勢體現(xiàn)在以下幾個方面：

1. 預處理階段：KMP算法首先對模式串進行預處理，生成next數(shù)組，這一步驟的時間復雜度為O(m)。
2. 匹配階段：在匹配過程中，當發(fā)現(xiàn)不匹配時，KMP算法利用next數(shù)組來決定模式串應該向右移動多少個字符，而不是簡單地回溯到下一個字符。
3. 避免回溯：由于KMP算法能夠利用next數(shù)組避免不必要的回溯，因此在最壞情況下也能保持較高的效率。

前綴表

在KMP算法中，next數(shù)組是一個關鍵的數(shù)據(jù)結構，它用于存儲模式串中每個位置之前的最長相等前后綴的長度。

1. 構建Next數(shù)組

首先，我們需要構建next數(shù)組，這個數(shù)組將存儲模式串中每個位置的最長相同前綴和后綴的長度。我們將next[0]初始化為0，因為模式串的第一個字符沒有前綴。

public class KMPMatcher {private String pattern;private int[] next;public KMPMatcher(String pattern) {this.pattern = pattern;next = new int[pattern.length()];computeNext();}// 構建Next數(shù)組private void computeNext() {int len = 0; // 最長相等前后綴的長度next[0] = 0; // next[0]初始化為0int i = 1;while (i < pattern.length()) {if (pattern.charAt(i) == pattern.charAt(len)) {len++;next[i] = len;i++;} else {if (len > 0) {len = next[len - 1];} else {next[i] = 0;i++;}}}}
}

• pattern：模式串，我們需要在其上構建next數(shù)組。
• next：用于存儲模式串的部分匹配結果的數(shù)組。
• computeNext方法：計算next數(shù)組的值。
  • len：記錄當前匹配的最長前后綴的長度。
  • 當pattern.charAt(i)等于pattern.charAt(len)時，增加len和i，并將next[i]設置為len。
  • 如果不相等且len大于0，len回溯到next[len - 1]。
  • 如果len為0，next[i]設置為0，i增加1。

2. 搜索匹配

接下來，我們使用構建好的next數(shù)組來搜索主串中是否存在模式串。

public int search(String text) {int i = 0; // 主串的索引int j = 0; // 模式串的索引while (i < text.length()) {if (j == pattern.length()) {return i - j; // 找到匹配，返回位置} else if (i < text.length() && pattern.charAt(j) == text.charAt(i)) {i++;j++;} else {if (j > 0) {j = next[j - 1];} else {i++;}}}return -1; // 未找到匹配
}

• search方法：在主串text中搜索模式串pattern。
  • i和j：分別為主串和模式串的索引。
  • 當j等于模式串長度時，表示找到匹配，返回匹配的起始位置。
  • 當text.charAt(i)等于pattern.charAt(j)時，兩個索引都增加。
  • 如果字符不匹配且j大于0，根據(jù)next數(shù)組回溯j。
  • 如果j為0，i增加1，繼續(xù)匹配。

這個實現(xiàn)中，next[0]被初始化為0，這與一些其他實現(xiàn)中next[0]初始化為-1有所不同。這種實現(xiàn)方式在邏輯上更直觀，因為next[0]表示模式串的第一個字符沒有前綴，所以其長度自然為0。