学步园

前言：在博客园中看到了阮一锋讲解KMP算法的文章以及园中另外一位博友写的JS版本的KMP算法，根据自己的理解，在这位博友的基础上改进了下。

代码如下：

/**
 * 生成部分匹配表
 */
function kmpGetPartMatchTable(targetStr){
    var aPartMatchTable = [];
    var tmpCompareLen = 0;
    var tmpPartMatchVal = 0;
    var prefix,suffix;//匹配串前缀,后缀
    for (var i = 0, j = targetStr.length; i < j; i++){
        if (i == 0){
            aPartMatchTable[i] = 0;
            continue;
        }
        tmpCompareLen = i; //匹配串前缀,后缀最大长度
        tmpPartMatchVal = 0;
        for (;tmpCompareLen > 0; tmpCompareLen--){
            prefix = targetStr.substr(0,tmpCompareLen);
            suffix = targetStr.substr(i-tmpCompareLen+1,tmpCompareLen);
            if (prefix == suffix){ //找到匹配串前缀,后缀最长的共有元素
                tmpPartMatchVal = prefix.length; //部分匹配值为:匹配串前缀,后缀最长的共有元素的长度
                break;
            }
        }
        aPartMatchTable[i] = tmpPartMatchVal;
    }
    return aPartMatchTable;
}

/**
 * KMP算法 查找字符串
 */
function KMP(sourceStr,targetStr){
    var partMatchValue = kmpGetPartMatchTable(targetStr); //部分匹配表
    var result = false;
    var i,j,m,n;
    n = targetStr.length;
    for(i=0,j=sourceStr.length;i<j;i++){
        for(var m=0;m<n;m++){
            if(targetStr.charAt(m) != sourceStr.charAt(i+m)){
                if ( (m > 0) && (partMatchValue[m-1] > 0) ){
                    i += (m-partMatchValue[m-1]-1); //设置外层循环开始位置
                }
                break;
            }
        }
        if (m == n){
            result = true;
            break;
        }
    }
    return result;
}
s = "BBC ABCDAB ABCDABCDABDE";
t = "ABCDABD";
console.log( KMP(s,t) );

 

参考链接

http://news.cnblogs.com/n/176771/

http://www.cnblogs.com/artwl/archive/2013/05/02/3054434.html