Javascript——KMP算法
KMP算法,全称Knuth-Morris-Pratt算法,是一种用于字符串匹配的算法,由Donald Knuth、Vaughan Pratt和James Morris发明。该算法的主要思想是通过预处理模式字符串,构建一个部分匹配表(也称为失配函数),然后利用该表进行模式匹配,从而实现高效的字符串匹配。KMP算法的用处非常广泛,包括但不限于以下几个方面:
- 字符串匹配:KMP算法可以用于在一个文本串中查找某个模式串的出现位置,这是字符串匹配的基本应用。在数据库查询、文件匹配等场景中,KMP算法可以快速找到符合条件的字符串。
- 字符串搜索:在搜索引擎或文本编辑器等应用中,KMP算法可以加快字符串搜索的速度,提高搜索效率。通过预处理模式串,减少了在文本串中的不必要的比较次数,从而提高了匹配效率。
- 编译器优化:在编译器优化中,KMP算法可以用于字符串匹配和替换,提高编译器的性能和效率。
- 数据压缩:在数据压缩领域,KMP算法可以用于字符串匹配和压缩,提高数据传输的效率和速度。
- 基因序列匹配:在生物信息学领域中,KMP算法可以用于匹配DNA或RNA序列,这对于基因序列分析和研究具有重要意义。
总的来说,KMP算法在实际项目中可以帮助提高字符串搜索、匹配和处理的效率,提升系统性能和用户体验。因此,掌握KMP算法并灵活运用在实际项目中是非常有益的。
KMP算法在字符串匹配将时间复杂度从O(m*n)->O(m+n),牺牲空间(计算next数组)
计算next数组后匹配到不相等的字符无需重新回退到开始位置,而是知道”跳“到指定位置
在KMP算法中,
next
数组(有时也称为π
表或前缀函数)用于存储部分匹配信息,以便在模式串与文本串不匹配时,模式串能够跳过一些不必要的字符比较,直接跳转到可能匹配的位置。
next数组计算流程:
- 初始化
- 前后缀不相同情况( 退到前一next,继续回溯【循环,直至匹配相等或者到起始位置】)
- 前后缀相同情况
- 更新next数组
const getNext = (needle) => { let next = []; let j = 0; next.push(j); for (let i = 1; i < needle.length; ++i) { while (j > 0 && needle[i] !== needle[j]) j = next[j - 1]; if (needle[i] === needle[j]) j++; next.push(j); } return next; }
- 初始化:
- 创建一个空数组
next
,用于存储部分匹配信息。- 初始化变量
j
为0,j
表示当前考察的模式串中的最长相同前缀后缀的长度(注意这里的j
实际上对应的是next
数组中的值,而不是索引)。- 将
j
(即0)推入next
数组,作为next[0]
的值。在KMP算法中,next[0]
通常设为-1或0,这里选择0是为了简化后续的逻辑处理(在某些实现中,next[0]
的值不会被直接使用,而是作为一个哨兵值)。- 遍历模式串:
- 使用一个
for
循环遍历模式串needle
的每个字符(从索引1开始,因为next[0]
已经初始化)。- 在每次迭代中,使用
while
循环来处理当前字符needle[i]
与needle[j]
不匹配的情况。如果它们不匹配,并且j
大于0(即不是模式串的开头),则将j
更新为next[j - 1]
的值,这表示回退到前一个可能匹配的位置。这个过程会一直持续到找到一个匹配或者j
变为0(即回退到模式串的开头)。- 如果当前字符
needle[i]
与needle[j]
匹配,则将j
自增,表示扩展了当前相同前缀后缀的长度。- 将更新后的
j
值推入next
数组,作为next[i]
的值。- 返回结果:
- 当
for
循环结束时,next
数组已经填充完毕,函数返回这个数组。
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (needle.length === 0)
return 0;
let next=getNext(needle);
let j=0;
for(let i=0;i<haystack.length;i++){
//字符匹配到不同的,回溯跳!!!while
while(j>0 && haystack[i]!==needle[j]){
j=next[j-1];//写成need[j-1],excuse me?
}
//相等时,继续往下匹配
if(haystack[i]===needle[j]){
j++;
}
//匹配成功,i此时仍指向最后一字符
//气死,length写出lenth,死都找不到那出错了
if(j===needle.length){
return i-needle.length+1;
}
}
//未找到
return -1;
};
var getNext=function(needle){
//初始化
let next=[];
let j=0;
next.push(j);
for(let i=1;i<needle.length;i++){
//前后缀不同,循环回溯
while(j>0&&needle[i]!==needle[j]){
j=next[j-1];
}
if(needle[i]===needle[j]){
j++;
}
next.push(j);
}
//记得返回出去!!!
return next;
}
/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function(s) {
let next=getNext(s);
//保证next大于0,即有最长前后缀,子串中除去最长前后缀的其他部分为最小重复字符串
//next[next.length-1] 表示整个字符串 s 的最长相等的前缀和后缀的长度。
//s.length % (s.length - next[next.length-1]) === 0 用于判断,除去这个最长相等的前缀和后缀
//剩下的部分(即重复的子串)是否能整除整个字符串的长度。如果可以整除,说明 s 是由这个更小的字符串重复构成的。
if(next[next.length-1]>0&&s.length%(s.length-next[next.length-1])===0)return true;
return false;
};
var getNext=function(s){
//初始化
let j=0;
let next=[];
next.push(j);
for(let i=1;i<s.length;i++){
//前后缀不相同
while(j>0&&s[i]!==s[j]){
//回溯
j=next[j-1];
}
//前后缀相同时
if(s[i]===s[j]) j++;
//更新next数组
next.push(j);
}
return next;
}
这段代码实现了一个函数
repeatedSubstringPattern
,用于判断一个字符串s
是否是由某个更小的字符串重复若干次构成的。下面是对代码及其注释的详细解释:函数
repeatedSubstringPattern
- 参数:接收一个字符串
s
。- 返回值:返回一个布尔值,如果字符串
s
是由某个更小的字符串重复若干次构成的,则返回true
;否则返回false
。函数内部逻辑
获取
next
数组:调用getNext(s)
函数来获取字符串s
的next
数组。next
数组是 KMP(Knuth-Morris-Pratt)算法中的一部分,用于记录字符串的前缀函数(即每个位置之前的字符串的最长相等的前缀和后缀的长度)。判断是否存在重复子串:
next[next.length-1]
表示整个字符串s
的最长相等的前缀和后缀的长度。- 如果
next[next.length-1] > 0
,说明s
至少有一个非空的前缀和后缀是相等的。s.length % (s.length - next[next.length-1]) === 0
用于判断,除去这个最长相等的前缀和后缀后,剩下的部分(即重复的子串)是否能整除整个字符串的长度。如果可以整除,说明s
是由这个更小的字符串重复构成的。函数
getNext
- 参数:接收一个字符串
s
。- 返回值:返回一个数组
next
,其中next[i]
表示字符串s
中从索引0
到i
的子串的最长相等的前缀和后缀的长度。函数
getNext
内部逻辑
初始化:设置
j = 0
(j
用于表示当前比较的前后缀长度),next
数组初始化为[0]
(next[0]
总是0
,因为空字符串是其自身的最长相等前缀和后缀)。遍历字符串:从索引
1
开始遍历字符串s
。前后缀比较:
- 如果
s[i]
不等于s[j]
,则回溯j
到next[j-1]
(因为next[j-1]
表示子串s[0...j-1]
的最长相等前缀和后缀的长度,我们可以从这个位置继续比较)。- 如果
s[i]
等于s[j]
,则j
自增,表示找到了更长的相等前缀和后缀。更新
next
数组:每次循环结束后,将当前的j
值添加到next
数组中。总结
这段代码利用了 KMP 算法中的
next
数组来判断一个字符串是否是由某个更小的字符串重复构成的。通过比较字符串的最长相等前缀和后缀,以及利用取余操作,实现了高效的判断逻辑。