1、几个最基本的概念
- 字符串的前缀： 主串（目标串）从索引0开始的子串被称为主串的前缀。
- 字符串的后缀： 主串从索引大于0的位置到结尾的子串称为主串的后缀。
- 目标串： 也称为主串，是比较长的字符串。
- 模式串： 也称为子串，是较短的字符串，用来在目标串中进行匹配。
- 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算法时间复杂度的详细讲解：
- 构建部分匹配表的时间复杂度： 构建部分匹配表的过程只需要遍历一次模式串，时间复杂度为O(m)。
- KMP匹配的时间复杂度： KMP算法的匹配阶段，在最坏情况下需要遍历整个目标串，但由于KMP算法的特性，它能够避免不必要的比较。具体而言，当模式串与目标串的某一部分不匹配时，KMP算法可以通过部分匹配表跳过一些已经比较过的字符。因此，在匹配阶段的总体时间复杂度为O(n)。
因此，KMP算法的总体时间复杂度为O(m + n)。相较于暴力算法的O((n-m+1) * m)来说，在目标串很长而模式串较短的情况下，KMP算法的性能更好。
