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

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

复制代码 代码如下:

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

您可能感兴趣的文章:

  • C语言实现字符串匹配KMP算法
  • c语言中使用BF-KMP算法实例
  • C#常见算法面试题小结
  • C#实现排列组合算法完整实例
  • c#冒泡排序算法示例
  • c#获取相同概率随机数的算法代码
  • c#哈希算法的实现方法及思路
  • C#的3DES加密解密算法实例代码
  • C# DES加密算法中向量的作用详细解析
  • C#实现协同过滤算法的实例代码
  • KMP算法的C#实现方法