1 喜欢

动画演示KMP字符串匹配算法

admin
admin
2021-04-27 07:54:52 阅读 338

参考链接

KMP算法

动画演示

KMP动画演示

参考代码

function genNext(pattern) { let len = pattern.length let next = [-1] let i = 0 let j = -1 while (i < len - 1) { if (j == -1 || pattern[i] == pattern[j]) { i++ j++ next[i] = j } else { j = next[j] } } return next } function kmp(target, pattern) { let pLen = pattern.length let tLen = target.length let i = 0 let j = 0 let next = genNext(pattern) while (j < pLen && i < tLen) { if (j === -1 || pattern[j] == target[i]) { i++ j++ } else { j = next[j] } } if (j === pLen) { return i - j } else { return -1 } } console.log(kmp("aaaacdbf", "cdbf"))

关于作者
admin
admin
admin@ifront.net
 获得点赞 42
 文章阅读量 38085
文章标签