复习一下KMP.

失配时:

  • i 不变,j 退回到 next[j] 位置;
  • 当 j 退到模式串第一个位置时,i、j 同时 +1. 表示s[i]和t[0]不匹配时,从s[i+1]重新匹配。

get_next :

1) 下标从0开始:

2) 下标从1开始:

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

3) 改进版:

当 t[i] == t[j] && t[i+1] == t[j+1] 时,next[++i] = next[++j]. 例:

理解:

假如当前求的是next[‘a‘],此时 i 指向 ‘b‘,j 指向 ‘b‘.

若按普通KMP,因为’b‘ == ‘b‘,故 next[‘a‘] 该为 2. 此时有一个问题:

在 ‘a‘ 处失配时,j 退回到位置 2 再次比较,其实这一步是没有必要的:

这是因为 ‘b’ != ‘a‘,而 ‘a‘ == ‘a‘,自然 ‘a‘ 不会等于主串中的 ‘b’。

故在程序中加入一句:if(s[i] == t[j] && s[i+1] == t[j+1]) next[++i] = next[++j];

void get_next(string t, int next[]){
    int m = t.size();
    if(m == 0) return;
  
    next[0] = -1;
    int i = 0, j = -1;
    while(i < m - 1){
        if(j == -1 || t[i] == t[j]){
            ++i, ++j;
            if(t[i] != t[j]) next[i] = j;
            else next[i] = next[j];
        }
        else j = next[j];
    }
}

KMP

int KMP(string s, string t){
    get_next(t, next);
 
    int i = 0, j = 0, n = s.size(), m = t.size();
    while(i < n && j < m){
        if(j == -1 || s[i] == t[j]) i++, j++;
        else j = next[j];
    }
    if(j >= t.size()) return i - t.size();
    else return -1;
}