一、求字符串循环节

字符串长度为n，字符串的next数组为ne[1-n]，那么字符串的循环节为 n-ne[n]。
XXXXXXX长度为ne[n], aaa的长度为字符串循环节的长度

推导过程：

aaaaXXXXXXXXXXXXXXX
    XXXXXXXXXXXXXXXaaaa   上下都表示模式串p, XXX部分表示最大相同前后缀

aaaaXXXXXXXXXXXXXXX
  |(aaaa)
  | XXXXXXXXXXXXXXXaaaa   上下都表示模式串p,所有上面的aaa部分与下面XXX前面相同位数部分相同

   (aaaa)
aaaaXXXXXXXXXXXXXXX
  |(aaaa)
  | XXXXXXXXXXXXXXXaaaa   下部的头部aaa的部分又与上面第二部分相同

...以此类推，所有部分都相同，故n - ne[n]为字符串循环节。

二、求所有公共前后缀

ne[i]存储的是1~i位置的最长的公共前后缀，当我们想求出此位置的所有与前缀相等的后缀时：
递归求即可：
i1 = ne[n]
i2 = ne[i1]
i3 = ne[i2]
…
实现代码：

for (int i = n; i != 0; i = ne[i];){
    printf("%d ", ne[i]);
}

三、 KMP算法完整代码

写法一：字符下标从1开始存储，j指针指向模式串正在匹配的前一个位置，即s[i] == p[j+1]

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
int n, m,ne[N];
char p[N], s[M];

/**
 * 
 * 课后补充：
 *  (1)  n - ne[n]: 表示字符串的循环节，例如ababab，n = 6, ne[6]
 *  (2) ne[i]是位置i的最长前后缀，当我们想求所有和前缀相等的后缀时
 *  处理方法：i2 = ne[n]
 *            i2 = ne[i1]
 *            i3 = ne[i2]
 */

int main()
{
    scanf("%d%s%d%s", &n,p+1,&m,s+1);
    // 字符串下标从1开始存储

    /** 补充内容
     *

        for (int i = 1; i <= n; i ++ ) cout << ne[i] << " ";
        puts("\n所有与前缀和相等的后缀长度：");
        for (int i = n; i != 0; i = ne[i])
            cout << ne[i] << "  ";  
    **/

    // 求 next 数组, i从2开始，i=1时ne[1] = 0;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j+1]) j = ne[j];
        if (p[i] == p[j+1]) j ++;
        ne[i] = j;
    }

    // 原串和匹配的指针的初始位置
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        // 当j指针(模式串匹配指针)还没有退回起点(j != 0) 且 当前位置没有匹配成功时
        while (j && s[i] != p[j+1]) j = ne[j];      // j 指针回到上一个最长的匹配成功的位置

        // 当前位置匹配成功时候，即while循环跳出的条件是s[i] == s[j+1]时：
        if (s[i] == p[j+1]) j ++;       // j指针后移继续匹配

        // 字串匹配完毕时
        if (j == n) {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

写法二： 字符下标从0开始存储， j指针指向当前正在匹配的元素即 s[i] == p[j]

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
int n,m, ne[N];
char p[N], s[M];

int main()
{
    scanf("%d%s%d%s", &n, p, &m, s);

    // 下标为0的写法 且 j指针指向正在匹配的元素
    for (int i = 1, j = 0; i < n; i ++ )
    {
        while (j  && p[i] != p[j]) j = ne[j-1];
        if (p[i] == p[j]) j ++;
        ne[i] = j;
    }
    for (int i = 0; i < n; i ++ ) cout << ne[i] << " ";
    // puts("");

    for (int i = 0, j = 0; i < m; i ++ )
    {
        while (j && s[i] != p[j]) j = ne[j- 1] ;
        if (s[i] == p[j]) j ++;

        if (j == n)
        {
            printf("%d ", i - j + 1);
            j = ne[j- 1] ;
        }

    }
}