KMP算法求串的循环节长度

next数组

next数组的作用: 在失配时, 应该将模板串的指针指向哪个位置

next数组的意义: 前面长度为i的字串中, 前后缀相等的最大长度

求法一

memset(next, 0, sizeof next);
int j = 0, k = -1;  // j前缀，k后缀
next[0] = -1;
while (j < m - 1) {
    if (k == -1 || T[j] == T[k]) {
        j++;
        k++;
        if (T[j] != T[k]) {
            next[j] = k;
        } else {
            next[j] = next[k];
        }
    } else {
        k = next[k];
    }
}

求法二

memset(next, 0, sizeof next);
for (int i = 1; i < m; i++) {
    int j = next[i];
    while (j != 0 && T[i] != T[j]) j = next[j];
    next[i + 1] = (T[i] == T[j]) ? j + 1 : 0;
}

两种写法的思想都是差不多的, 要利用已经求好的数组加速向前跳

求循环节

最后next[n]表示的就是整个字符串前后缀相等的长度

显然, 对于某个字符串T，长度为n，由长度为l的字符串s重复k次得到，当k >= 2时必然有T.substr(0, n - l - 1) == T.substr(l, n - l - 1). 由于next表示的是前后缀的最长长度, 因此在已知T是循环串的情况下, 一个循环节的长度就是n - next[n].

若T不是一个完美的循环串, 其最后一个循环节缺失了一部分, 以上写法依然可以得到正确的循环节长度, T再补上l - n % l的长度就是循环串了

本文采用署名-相同方式共享 4.0 国际许可协议，转载请注明出处。