KMP算法用JavaScript实现
2024-10-19 02:21:30
KMP算法是字符串匹配的经典算法，简称 看毛片， 理论知识请直接看阮一峰老师的这篇文章，我看完文章之后尝试对算法进行了实现。
一句话总结KMP算法的核心思想：就是跳过已经对比的部分
而KMP算法的核心组成就是部分匹配表 + 回退算法。
部分匹配表1.0版本
function KMPpartMatchTable(str) {
var matchTable = [0];
var prefix = [],
suffix = [];
for(var i = 1; i < str.length; i++) {
prefix = getPrefix(str.substr(0, i + 1))
suffix = getSuffix(str.substr(0, i + 1))
var ret = [0]; //默认设置一个0,防止-Infinity
//对比2个数组，是否有重复的
prefix.forEach(function(n, i) {
for(var j = i; j < suffix.length; j++) {
if(n == suffix[j]) {
ret.push(n.length)
}
}
})
matchTable.push(Math.max.apply(null, ret))
}
//生成前缀数组
function getPrefix(s) {
let ret = []
for(var len = s.length; len > 0; len--) {
if(len == s.length) continue;
ret.push(s.substring(0, len))
}
return ret.reverse();
}
//生成后缀数组
function getSuffix(s) {
let ret = []
for(var len = s.length; len > 0; len--) {
if(len == s.length) continue;
ret.push(s.substring(len, s.length))
}
return ret.reverse();
}
return matchTable
}
这是我第一版写出来的，可以看到2个getPrefix和getSuffix有大部分是重复的代码。方便理解。需要for循环2次字符串，但不利于性能。所以可以将他们进行精简合并为1次
部分匹配表2.0版本
function KMPpartMatchTable(str) {
var matchTable = [0];
var prefix = [],
suffix = [];
for(var i = 1; i < str.length; i++) {
// prefix = getPrefix(str.substr(0, i + 1))
// suffix = getSuffix(str.substr(0, i + 1))
var s = str.substr(0, i + 1);
for(var len = s.length; len > 0; len--) {
if(len == s.length) continue;
prefix.push(s.substring(0, len)) //前缀数组
suffix.push(s.substring(len, s.length)) //后缀数组
}
var ret = [0]; //默认设置一个0,防止-Infinity
//对比2个数组，是否有重复的
prefix.forEach(function(n, i) {
for(var j = i; j < suffix.length; j++) {
if(n == suffix[j]) {
ret.push(n.length)
}
}
})
matchTable.push(Math.max.apply(null, ret))
}
return matchTable
}
KMPpartMatchTable('ABCDABD')//[0,0,0,0,1,2,0]
改进过后，逻辑没那么直观了。但一次字符串for循环就生成出了前缀和后缀数组
回退算法
function KMP(sourceStr, targetStr) {
var partMatchValue = KMPpartMatchTable(targetStr); //拿到匹配表
var result = false;
for(var i = 0; i < sourceStr.length; i++) {
for(var k = 0; k < targetStr.length; k++) {
if(str.charAt(k) == sourceStr.charAt(i)) {
if(k == targetStr.length - 1) {
result = true;
break;
} else {
i++;
}
} else {
if(k > 0 && partMatchValue[k - 1] > 0) {
k = partMatchValue[k - 1] - 1;
} else {
break;
}
}
}
if(result) {
break;
}
}
return result
}
var ss = 'ABCDAB ABCDAB ABCDAABCABCDABDABCDABDDABDBD'
var str = 'ABCDABD'
console.log(KMP(ss, str)) //true
最新文章
- c#日期格式化
- mycat高可用方案
- git 简单使用
- Unity : Ran out of trampolines of type 2
- 【OpenCV】图像的遍历
- AngularJS学习--- 事件处理(Event Handlers) ng-click操作 step 10
- MySQL Replication的相关文件
- SQL—— 事务
- Go原子计数
- SqlBulkCopy 数据批量操作使用的类
- HDU-2149 Public Sale
- github上排名靠前的java项目之_storm
- Android自己定义控件（状态提示图表）
- cocos2dx A* + tiledMap
- 汉字转全拼音函数优化方案(SQLServer),值得你看看
- jQuery的拾色器
- [置顶]【实用 .NET Core开发系列】- 导航篇
- Powerdesigner+PostgreSQL
- Servlet版本冲突引起的Error
- react和redux版本不匹配