【从 MP 算法到 KMP 算法】

在 MP 算法中，介绍了求 next 数组的步骤，但其仍存在一个缺陷

以下图为例，文本串 T='ABACBCDHI'，模式串 P="ABAB"，模式串的 next 数组为 next[4]={-1,0,0,1}

当出现文本串的字符 C 与模式串的字符 B 不匹配时，应将模式指针 $j$ 移动到位置 $1$

但从上图中不难发现，由于文本串的 C 以及和模式串的最后的字符 B 已经不匹配了，那么其与模式串前面的 B 也一定是不匹配的，因此，这一步是没有意义的

由此， D.E.Knuth 在 MP 算法上进行了改进，即 KMP （Knuth-Morris-Pratt ）算法

【nextVal 数组】

next 数组与 nextVal 数组

显然，问题发生在 $next[j]=k$ 这一步上，因此，可以加一个条件，当 $P[j]=P[k]$ 时，直接跳过，即令：

$next[j]=next[k]$

采用上述方法得到的 next 数组，即为 KMP 算法下的 next 数组，为与 MP 算法中的 next 数组区分，常称为 nextVal 数组

以 aaaab 为例，给出其 next 数组与 nextVal 数组

编号	0	1	2	3	4
string	a	a	a	a	b
next	-1	0	1	2	3
nextVal	-1	-1	-1	-1	3

nextVal 数组的实现

与求 next 数组相比，求 nextVal 数组与其几乎完全相同，唯一的区别就是当 $P[j]=P[k]$ 时，将 $next[j]=k$ 改为 $next[j]=next[k]$

计算 nextVal 数组的代码如下：

int nextVal[N];
void getNextVal(char P[]) { //获取字符数组p的nextVal数组
    nextVal[0] = -1;        //初始化

    int len = strlen(P); //模式串长度
    int j = 0;           //模式指针j
    int k = -1;          //位置k

    while (j < len) {
        if (k == -1) { //初始化时
            k++;       //此前有nextVal[j]=k
            j++;       //指针后移
            nextVal[j] = k;
        } 
        else if (P[j] == P[k]) { //nextVal[j] = nextVal[k]
            k++;                 //此前有nextVal[j]=k
            j++;                 //指针后移
            nextVal[j] = nextVal[k];
        } 
        else { //k=nextVal[k]
            k = nextVal[k];
        }
    }
}

【KMP 算法的匹配】

MP 算法与 KMP 算法的区别仅在于 next 数组的不同，在匹配时，KMP 与 MP 的匹配过程相同


int MP(char T[], char P[]) { //KMP算法
    int tLen = strlen(T);    //文本串长度
    int pLen = strlen(P);    //模式串长度

    int i = 0;  //文本串指针
    int j = 0;  //模式串指针

    getNextVal(P); //获取KMP的nextVal数组

    while (i < tLen && j < pLen) {
        if (j == -1 || T[i] == P[j]) { //当j=-1时，要移动的是i，同样j也要归零
            i++;
            j++;
        } else {
            j = nextVal[j]; //j回到指定位置
        }
    }

    if (j == pLen) //匹配成功
        return i - j;
    return -1;
}

【KMP 算法的应用】

KMP 算法的核心是求 next 数组，其除了用于单模式匹配外，还可用来求模式串的出现次数、最小循环节的长度

求模式串出现次数

若想求模式串 P 出现的次数，仅需在进行匹配时，当模式串 P 匹配成功后记录一次次数即可

需要注意的是，在匹配成功后，是否要初始化模式串指针位置要根据实际问题情况来判断

int KMP(char T[], char P[]) {
    int tLen = strlen(T);
    int pLen = strlen(P);
    getNext(P);

    int res = 0;
    int j = 0;  //初始化在模式串的第一个位置
    for (int i = 0; i < tLen; i++) { //遍历文本串
        while (j && P[j] != T[i]) { //顺着失配边走，直到可以匹配，最坏情况是j=0
            j = next[j];
        }
        if (P[j] == T[i]) { //匹配成功，继续下一个位置
            j++;
        }
        if (j == pLen) { //计算模式串在文本串中出现的次数
            res++;
            /*
                若可使用重复字符，下面的j=0需注释掉
                若不可使用重复字符，下面的j=0无需注释
                原因：是否需要初始化模式串指针位置
            */
            j = 0;
        }
    }

    return res;
}

求最小循环节长度

对于 next数组来说，next[j] 代表当前字符 $j$ 之前的字符串中，最大前缀与后缀的匹配数，即：next[j]=k 代表 $j$ 之前的字符串中有最大长度为 $k$ 的相同前缀后缀

例如：

i	0	1	2	3	4	5
p[i]	a	b	c	b	a
next[i]	-1	0	0	0	0	1

对于长度为 $n$ 的模式串，由于 $next[j]=k$ 表示 $p[1..i-1]$ 最大前缀与后缀的匹配数，那么，模式串第 $1$ 位到第 $next[n]$ 位与模式串第 $n-next[n]$ 位到第 $n$ 位是匹配的

因此，当 $next[j]>0$ 时，$j-next[j]$ 为字符串匹配时移动的位数

故而当 $n%(n-next[n])=0$ 时，说明模式串中存在重复连续的子串，且其长度为

$len=n-next[n]$

进而可得字符串的最小周期为

$T=\frac{n}{len}=\frac{n}{n-next[n]}$

int next[N];
int main() {
    char P[N];
    scanf("%s", P);
    
    int n = strlen(P); //模式串长度
    getNext(P);        //获取next数组

    int len = n - next[n]; //与前缀相同的后缀长度
    if (n % len == 0) {    //存在循环节
        int res = n / len; //循环节长度
        printf("%d\n", res);
    } 
    else //不存在循环节，长度为1
        printf("1\n");
    return 0;
}