目錄

1、幾個最基本的概念

2、暴力算法?

3、KMP算法?

4、KMP代碼實現

5、時間復雜度

---

1、幾個最基本的概念

1. 字符串的前綴： 主串（目標串）從索引0開始的子串被稱為主串的前綴。

2. 字符串的后綴： 主串從索引大于0的位置到結尾的子串稱為主串的后綴。

3. 目標串： 也稱為主串，是比較長的字符串。

4. 模式串： 也稱為子串，是較短的字符串，用來在目標串中進行匹配。

5. KMP算法的目的： 以O(m+n)的時間復雜度，在目標串中找到模式串，并返回模式串在目標串中的第一個字符的索引位置。其中，m為模式串的長度，n為目標串的長度。

2、暴力算法?
?

暴力算法是一種簡單直觀但效率較低的字符串匹配算法。其基本思想是，對于目標串的每一個可能的起始位置，都嘗試將模式串與目標串進行比較，直到找到匹配或者遍歷完整個目標串。以下是暴力算法的詳細講解：

public class BruteForce {// 暴力匹配算法public static int bruteForceSearch(String text, String pattern) {int n = text.length();int m = pattern.length();// i為目標串的起始位置for (int i = 0; i <= n - m; i++) {int j;// j為模式串的索引，用于和目標串的子串進行比較for (j = 0; j < m; j++) {if (text.charAt(i + j) != pattern.charAt(j)) {break;  // 如果不匹配，退出內循環}}if (j == m) {return i;  // 找到匹配，返回起始位置}}return -1;  // 未找到匹配}public static void main(String[] args) {String text = "ABABDABACDABABCABAB";String pattern = "ABABCABAB";int index = bruteForceSearch(text, pattern);if (index != -1) {System.out.println("匹配成功，起始位置：" + index);} else {System.out.println("未找到匹配");}}
}

3、KMP算法?

KMP算法（Knuth-Morris-Pratt算法）是一種用于字符串匹配的經典算法，它能夠在文本串和模式串不匹配的情況下，通過已經匹配的部分信息，避免將模式串移動到所有可能的位置進行匹配，從而提高匹配效率。下面我將用Java語言詳細講解KMP算法的實現。

KMP算法的關鍵在于構建一個部分匹配表（Partial Match Table），該表記錄了模式串每個位置的最長前綴和最長后綴的匹配長度。這個表可以幫助算法在匹配失敗時，跳過一些不可能匹配的位置，從而減少匹配次數。

4、KMP代碼實現

public class KMP {// 構建部分匹配表private static int[] buildPartialMatchTable(String pattern) {int[] lps = new int[pattern.length()];int len = 0;  // 當前最長匹配前綴和后綴的長度for (int i = 1; i < pattern.length(); ) {if (pattern.charAt(i) == pattern.charAt(len)) {len++;lps[i] = len;i++;} else {if (len != 0) {len = lps[len - 1];} else {lps[i] = 0;i++;}}}return lps;}// KMP匹配算法public static int kmpSearch(String text, String pattern) {int[] lps = buildPartialMatchTable(pattern);int i = 0;  // text的索引int j = 0;  // pattern的索引while (i < text.length()) {if (pattern.charAt(j) == text.charAt(i)) {i++;j++;}if (j == pattern.length()) {// 匹配成功return i - j;} else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {// 不匹配時，根據部分匹配表跳過一些可能不匹配的位置if (j != 0) {j = lps[j - 1];} else {i++;}}}// 沒有找到匹配return -1;}public static void main(String[] args) {String text = "ABABDABACDABABCABAB";String pattern = "ABABCABAB";int index = kmpSearch(text, pattern);if (index != -1) {System.out.println("匹配成功，起始位置：" + index);} else {System.out.println("未找到匹配");}}
}

5、時間復雜度

KMP算法的時間復雜度為O(m + n)，其中m是模式串的長度，n是目標串的長度。相較于暴力算法，KMP算法在大多數情況下具有更好的性能。

下面是對KMP算法時間復雜度的詳細講解：

1. 構建部分匹配表的時間復雜度： 構建部分匹配表的過程只需要遍歷一次模式串，時間復雜度為O(m)。

2. KMP匹配的時間復雜度： KMP算法的匹配階段，在最壞情況下需要遍歷整個目標串，但由于KMP算法的特性，它能夠避免不必要的比較。具體而言，當模式串與目標串的某一部分不匹配時，KMP算法可以通過部分匹配表跳過一些已經比較過的字符。因此，在匹配階段的總體時間復雜度為O(n)。

因此，KMP算法的總體時間復雜度為O(m + n)。相較于暴力算法的O((n-m+1) * m)來說，在目標串很長而模式串較短的情況下，KMP算法的性能更好。