4-4 试说明KMP算法中求解next数组值的方法。

[问答题]

于超

void getNext(string t, int *next){
    int i = 0, j = -1;
    next[0] = -1;
    while(i < t.length()){
        if(j == -1 || t[i] == t[j]){
            ++i;
            ++j;
            next[i] = j;
        }else
            j = next[j];
    }
}

模式串自身进行前缀和后缀匹配，当匹配失效时回溯j的值，回溯的位置刚好是next[j]，而且可能出现连续回溯，直到可以继续匹配或回溯到第一个元素，也就是j = next[0] = -1。

发表于 2020-07-01 20:15:46 回复(0)