KMPAlgorithm

Next数组

设主串 S, 模式串 T, 则 Next[j] = k 表示当模式串的第 i 个字符发生失配时，即 S[i] $\neq$ T[j], 则下一个需匹配的位置为 k, 即继续比较 S[i] 与 T[k] 保证主串指针 i 不回溯。

• 求解 Next 数组
  • 若有 Next[j] = k, 求 Next[j+1]
  • Next[j] = k 解释：S[i] $\neq$ T[j] $\Longrightarrow$ Compare(S[i], T[k]), 且 S[i-k,…,i-1] = T[1,…,k-1]
  • 若 T[j+1] = T[j], j = next[j], 则可以延续上一个匹配位置一个字符，可以理解为公共子串增一，因此 Next[j+1] = j+1;

void get_next(string t, int &next[])
{
    int i=1, j=0;
    next[1] = 0;
    while(i <= strlen(T)){
        if(j == 0 || T[i] == T[j]){
            i++, j++;
            next[i] = j;
        }
        else j = next[j];
    }
}

改进 Next 数组

void get_nextval(string T, int &nextval[])
{
    int i=1, j = 0;
    nextval[1] = 0;
    while(i < strlen(T)){
        if(j==0||T[i] == T[j]){
            ++i, ++j;
            if(T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}