资料

讲的最好的kmp原理篇
讲解next[]推导

朴素模式

//字符串匹配的朴素算法
//长字符串s，从下标pos处开始，查找后续是否存在字符串t(仅第一匹配成功的),返回匹配成功的下标，否则返回-1
function indexof(s,t,pos){
    var slen = s.length;
    var tlen = t.length;
    for(var i = pos;i<=slen-tlen;i++){
        var j ;
        for(j=0;j<tlen;j++){
            if(s.charAt(i+j) != t.charAt(j)){
                break;
            }
        }
        if(j==tlen){
            return i;
        }

    }
    return -1;
}
indexof('ksdfnnksf','nk',0);

//第二种写法，便于后续理解kmp匹配算法
function indexof2(s,t,pos){
    var slen = s.length;
    var tlen = t.length;
    var i = pos;
    var j = 0;
    while(i < slen && j < tlen){

        if(s.charAt(i) == t.charAt(j)){
            i++;
            j++;
        }else{
            i = i-j+1;
            j = 0;

        }

    }
    if(j>=tlen){
        return i-tlen;

    }else{
        return -1;
    }
}

indexof2('ksdnfnksf','nk',0);

KMP模式

//kmp模式匹配算法
//相比较于朴素算法，减少不必要的重复比较，使得效率更高
//核心：每轮比较后，使得i不回溯，j值取决于t串内部的重复程度。
function getNext(t){
    var next = [];
    next[0] = -1;//当s[i] != t[j]时，j=0,则-1代表直接i+1,j=0,继续比较
    var m = 0;//后缀
    var n = -1;//前缀
    while(m < t.length-1){//每次算next[j]时，都是看的t[0]-t[j-1]中的最大前缀后缀子序列，这里j-1 = m
        if(n == -1 || t.charAt(m) == t.charAt(n)){//表示前缀的单个字符等于后缀的单个字符
            ++m;
            ++n;

            if(t.charAt(m) == t.charAt(n)){//改进的地方
                next[m] = next[n];
            }else{
                next[m] = n;
            }

        }else{//若字符不等，则n回溯
            n = next[n];
        }

    }
    return next;
}
function indexof3(s,t,pos){
    var slen = s.length;
    var tlen = t.length;
    var next = getNext(t);
    var i = pos;
    var j = 0;
    while(i < slen && j < tlen){

        if(j == -1 ||s.charAt(i) == t.charAt(j)){
            i++;
            j++;
        }else{
            //j根据next数组回溯，i不回溯
            j = next[j];

        }

    }
    if(j>=tlen){
        return i-tlen;

    }else{
        return -1;
    }
}