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数组来判断一个字符串是否是由某个更小的字符串重复构成的。通过比较字符串的最长相等前缀和后缀，以及利用取余操作，实现了高效的判断逻辑。