基于KMP算法JavaScript的实现方法分析

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基于KMP算法JavaScript的实现方法分析，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1643字，纯文字阅读大概需要3分钟。

内容图文

算法的核心是部分匹配表和回退算法，部分匹配表的实现如下：
代码如下:
function kmpGetStrPartMatchValue(str) {
    var prefix = [];
    var suffix = [];
    var partMatch = [];
    for(var i=0,j=str.length;i<j;i++){
        var newStr = str.substring(0,i+1);
        if(newStr.length == 1){
            partMatch[i] = 0;
        } else {
            for(var k=0;k<i;k++){
                prefix[k] = newStr.slice(0,k+1);
                suffix[k] = newStr.slice(-k-1);
                if(prefix[k] == suffix[k]){
                    partMatch[i] = prefix[k].length;
                }
            }
            if(!partMatch[i]){
                partMatch[i] = 0;
            }
        }
    }
    prefix.length = 0;
    suffix.length = 0;
    return partMatch;
}

//demo
var t="ABCDABD";
console.log(kmpGetStrPartMatchValue(t));
//output:[0,0,0,0,1,2,0]

回退算法实现如下：
代码如下:
function KMP(sourceStr,targetStr){
    var partMatchValue = kmpGetStrPartMatchValue(targetStr);
    var result = false;
    for(var i=0,j=sourceStr.length;i<j;i++){
        for(var m=0,n=targetStr.length;m<n;m++){
            if(str.charAt(m) == sourceStr.charAt(i)){
                if(m == targetStr.length-1){
                    result = true;
                    break;
                } else {
                    i++;
                }
            } else {
                if(m>0 && partMatchValue[m-1] > 0){
                    m = partMatchValue[m-1]-1;
                } else {
                    break;
                }
            }
        }
        if(result){
            break;
        }
    }
    return result;
}
var s = "BBC ABCDAB ABCDABCDABDE";
var t = "ABCDABD";
console.log(KMP(s,t));
//output: true

内容总结

以上是互联网集市为您收集整理的基于KMP算法JavaScript的实现方法分析全部内容，希望文章能够帮你解决基于KMP算法JavaScript的实现方法分析所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端