y总算法竞赛写法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010 , M = 1000010;
int ne[N] , n , m;
char p[N] , s[M];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    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++)
    {
        while(j && s[i] != p[j + 1])j = ne[j];
        if(s[i] == p[j + 1])j ++;
        if(j == n)printf("%d ",i - n);
    }
    return 0;
}

408写法

对比一下：（next数组整体减去1和不减都对）

如何求nextval数组（优化后）