字符串匹配——KMP算法

前言
刷到字符串匹配的力扣题了【28. 实现 strStr() 】，这题简单吧用库函数做就可以，说难吧，就得引出大名鼎鼎的线性匹配算法——KMP。

KMP

算法背景与原理

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

在传统的字符串匹配算法中，如Brute Force方法，一旦发现不匹配，模式串会回溯到下一个起始位置重新开始匹配。这种方法在最坏情况下的时间复杂度为O(nm)，其中n是主串长度，m是模式串长度。而KMP算法通过预处理模式串，构造一个部分匹配表（也称为next数组），在发生不匹配时，可以跳过已经确认不会匹配的部分，从而提高匹配效率。

核心思想:由传统双层循环遍历入手优化时间复杂度，优化的手段是借助前缀表保证外层索引单向移动。

算法优势

KMP算法的主要优势在于其时间复杂度为O(n+m)，相比传统的Brute Force方法，KMP算法在最坏情况下也能保持较高的效率。这是因为KMP算法利用了已经匹配的信息来避免不必要的重复比较。具体来说，KMP算法的优势体现在以下几个方面：

1. 预处理阶段：KMP算法首先对模式串进行预处理，生成next数组，这一步骤的时间复杂度为O(m)。
2. 匹配阶段：在匹配过程中，当发现不匹配时，KMP算法利用next数组来决定模式串应该向右移动多少个字符，而不是简单地回溯到下一个字符。
3. 避免回溯：由于KMP算法能够利用next数组避免不必要的回溯，因此在最坏情况下也能保持较高的效率。

前缀表

在KMP算法中，next数组是一个关键的数据结构，它用于存储模式串中每个位置之前的最长相等前后缀的长度。

1. 构建Next数组

首先，我们需要构建next数组，这个数组将存储模式串中每个位置的最长相同前缀和后缀的长度。我们将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数组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数组。
• next：用于存储模式串的部分匹配结果的数组。
• computeNext方法：计算next数组的值。
  • 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数组来搜索主串中是否存在模式串。

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，根据next数组回溯j。
  • 如果j为0，i增加1，继续匹配。

这个实现中，next[0]被初始化为0，这与一些其他实现中next[0]初始化为-1有所不同。这种实现方式在逻辑上更直观，因为next[0]表示模式串的第一个字符没有前缀，所以其长度自然为0。