KMP算法的JS实现

talk is cheap，show me the code：

function kmpGetStrPartMatchValue(str) {
    var prefix = [];
    var suffix = [];
    var partMatch = [];
    for(var i=0;i<str.length;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;
}
function KMP(sourceStr,targetStr){
    var partMatchValue = kmpGetStrPartMatchValue(targetStr);
    var result = false;
    for(var i=0;i<sourceStr.length;i++){
        for(var m=0;m<targetStr.length;m++){
            if(targetStr.charAt(m) == sourceStr.charAt(i)){
                if(m == targetStr.length-1){
                    result = i-m;
                    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 ABCDABDDABDE";
var t = "ABCDABD";
console.log(kmpGetStrPartMatchValue(t));//[0, 0, 0, 0, 1, 2, 0]
console.log(KMP(s,t));//11

参考链接：

阮一峰-字符串匹配的KMP算法
[KMP算法的JavaScript实现
]