apache 多个网站,攀枝花网站推广,建设一个网站的具体步骤,百安居装修官网前言 刷到字符串匹配的力扣题了【28. 实现 strStr() 】#xff0c;这题简单吧用库函数做就可以#xff0c;说难吧#xff0c;就得引出大名鼎鼎的线性匹配算法——KMP。 目录 KMP 算法背景与原理算法优势 前缀表1. 构建Next数组2. 搜索匹配 KMP
算法背景与原理
KMP#x… 前言 刷到字符串匹配的力扣题了【28. 实现 strStr() 】这题简单吧用库函数做就可以说难吧就得引出大名鼎鼎的线性匹配算法——KMP。 目录 KMP 算法背景与原理算法优势 前缀表1. 构建Next数组2. 搜索匹配 KMP
算法背景与原理
KMPKnuth-Morris-Pratt算法是一种高效的字符串匹配算法由Donald Knuth、Vaughan Pratt等人在1977年提出。该算法的核心思想是避免在字符串匹配过程中不必要的回溯从而提高匹配效率。
在传统的字符串匹配算法中如Brute Force方法一旦发现不匹配模式串会回溯到下一个起始位置重新开始匹配。这种方法在最坏情况下的时间复杂度为O(nm)其中n是主串长度m是模式串长度。而KMP算法通过预处理模式串构造一个部分匹配表也称为next数组在发生不匹配时可以跳过已经确认不会匹配的部分从而提高匹配效率。 核心思想:由传统双层循环遍历入手优化时间复杂度优化的手段是借助前缀表保证外层索引单向移动。 算法优势
KMP算法的主要优势在于其时间复杂度为O(nm)相比传统的Brute Force方法KMP算法在最坏情况下也能保持较高的效率。这是因为KMP算法利用了已经匹配的信息来避免不必要的重复比较。具体来说KMP算法的优势体现在以下几个方面
预处理阶段KMP算法首先对模式串进行预处理生成next数组这一步骤的时间复杂度为O(m)。匹配阶段在匹配过程中当发现不匹配时KMP算法利用next数组来决定模式串应该向右移动多少个字符而不是简单地回溯到下一个字符。避免回溯由于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大于0len回溯到next[len - 1]。如果len为0next[i]设置为0i增加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为0i增加1继续匹配。
这个实现中next[0]被初始化为0这与一些其他实现中next[0]初始化为-1有所不同。这种实现方式在逻辑上更直观因为next[0]表示模式串的第一个字符没有前缀所以其长度自然为0。
