javascript实现KMP算法（没啥实用价值，只供学习）
2024-04-03 14:28:19
简单粗暴上代码
KMP的原理我就不讲了，想转过弯儿来不容易，建议大家先学会了怎么推导出next数组规律，然后准备两张纸，大纸上写上一行你要匹配的目标字符串，并分别写出位置编号，小纸上写上一行，也写上位置编号和对应的next数组编号，然后移动小纸片模拟匹配过程，你就会了。（用画图模拟也行）
从以上推导过程就能发现KMP算法的规律，得到如下代码：
推导next数组代码：
function getNext(str){
var i=1,j=0;
var next = [null,0];
while(i<str.length){
if(j==0 || str[i]==str[j]){
++i;
++j;
next[i] = j;
console.log('匹配到公共前缀：',`str[i]=${str[i]},str[j]=${str[j]} => i=${i},j=${j} next数组为${next}`)
} else {
console.log('无公共前缀：',`str[i]=${str[i]},str[j]=${str[j]} => j=next[j]=${next[j]} next数组为${next}`)
j = next[j];
}
}
return next;
}
KMP字符匹配算法
String.prototype.KMPsearch = function (str) {
var len = str.length;
var sstr = this.toString();
var slen = sstr.length;
var i = 0, j = 0, k = 0;
if (slen > 1) {
var next = KMPfunc(this.toString());
while (i < len) {
if (str[i] === sstr[j]) {
if (j == (slen - 1)) {
if (i == (len - 1)) {
return k + 1;
}
else {
k++;
j = 0;
}
}
else {
j++;
i++;
}
}
else if (i == (len - 1) && str[i] != sstr[i]) {
return k;
}
else {
if (j == 0) {
i++;
}
else {
j = next[j - 1];
}
}
}
}
else {
for (var i = 0; i < len; i++) {
if (sstr == str[i]) {
k++;
}
}
return k;
}
};
最新文章
- ABP理论学习之Web API控制器（新增）
- 转发 eclipse 取消javascript 验证
- GridView点击排序
- [ios][swift]Swift - 常用文件目录路径获取（Home目录，文档目录，缓存目录等）
- MFC编程入门之五(MFC消息映射机制概述)
- [转]diskpart命令
- mongodb gdal 矢量数据格式驱动
- 关于Chrome（谷歌浏览器）对docume,准确获取网页客户区的宽高、滚动条宽高、滚动条Left和Top
- spark基本概念
- asp.net mvc 上传图片流存服务器
- c#关于EXCEL导出数据库的做法
- Selenium Locating Elements
- 16重新安装HA0.63
- 大话C#之委托
- 无线网络中信噪比(SNR)计算
- Matplotlib学习---matplotlib的一些基本用法
- Flume配置文件写法总结
- Otto.de：我为什么选择分布式垂直架构
- maven学习三
- A标签添加JS事件，不跳转不刷新办法