基于KMP算法JavaScript的实现方法分析_基础知识-js教程-PHP中文网

基于KMP算法JavaScript的实现方法分析_基础知识

php中文网

发布： 2016-05-16 17:34:50

原创

1202人浏览过

算法的核心是部分匹配表和回退算法，部分匹配表的实现如下：

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

网梦购物系统

一套功能完善、性能稳定的经典网上购物系统，掌握了一整套从算法，数据结构到产品安全性方面的领先技术，使程序无论在安全性、负载能力方面均获得了成功，新版购物系统集成多种在线支付方式，全后台操作管理，并集成了Ewebedit编辑器，即使只有电脑基础知识的人也能够轻松操作和管理部分新增功能：集成多种网上支付形式，后台灵活切换增加Ewebedit编辑器，添加信息更容易！简洁、明快、新颖的界面，给人以美的感觉

查看详情

回退算法实现如下：

复制代码代码如下:

function KMP(sourceStr,targetStr){
    var partMatchValue = kmpGetStrPartMatchValue(targetStr);
    var result = false;
    for(var i=0,j=sourceStr.length;i        for(var m=0,n=targetStr.length;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