KMP算法

字符串匹配较快的算法

时间复杂度O(n)

代码

void get_next(SString T,int next[]){
    int i=1;
    int j =0;
    next[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {  //第一个或者是匹配成功
            i++;j++;
            next[i] = j;
        } else
            j = next[j];  //匹配不成功时,j退回next[j]
    }
}

int Index_KMP(SString S,SString T,int pos){
    int next[MAXSTRLEN];
    int i =1;
    int j = 1;
    get_next(T, next);
    while (j <= T[0] && i <= S[0]) { //第一个或者是匹配成功
        if (j == 0 || T[j] == S[i]) {
            i++;
            j++;
        } else{
            j = next[j];   ////匹配不成功时,j退回next[j]
        }
    }
    if(j>T[0]) return (i - T[0]);
    else return 0;
}
i 1 2 3 4 5 6 7
pattern a b c a b a d
next[i] 0 1 1 1 2 3 2

next[1] 一定是0
next[2] 一定是1