C++ 代码

例如：
S = “abababc”
P = “abababab”
p的next数组为：ne = [0,0,1,2,3,4,5,6]
1. next数组的意义：p字符串的每一个位置对应的最小回退长度
2. 回退一步的意义：返回到最长的前面部分已经匹配的长度对应的下标
3. 求next数组方法与kmp匹配方法类似

# include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
char s[M], p[N];
int ne[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    //求next的过程
    for (int i = 2, j = 0; i <= n; i ++)
    {
        while (j && p[i] != p[j + 1]) j = ne[i];
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }
    //KMP匹配过程
    for (int i = 1, j = 0; i <= m; i ++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p [j + 1]) j ++;
        if (j == n) // 匹配成功
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}