next数组写的有点不一样。。。 https://www.luogu.com.cn/record/55709545

#include<iostream>
#include<string>
using namespace std;
const int N=1e6+10;
int d[N];
string s1,s2;
void calc_D(string p, int lp)
{
    int i = 1, j = 0;
    while(i < lp)
    {
        if(p[i] == p[j])
            d[i ++] = ++ j;
        else 
        {
            if(j > 0)j = d[j - 1];
            else i ++;
        }
    }
}
int KMP(string t, int lt, string p, int lp)
{
    int i = 0, j = 0;
    while(i < lt)
    {
        if(t[i] == p[j])
        {
            i ++, j ++;
            if(j == lp)
            {
                cout<< i - j + 1 <<endl;
                i = i - j + 1;
                j = 0;
            }
        }
        else
        {
            if(j > 0) j = d[j - 1];
            else i ++;
        }
    }
    return -1;
} 
int main()
{
    ios::sync_with_stdio(false);
    cin>> s1 >> s2;
    int lt = s1.size(), lp = s2.size();
    calc_D(s2, lp);
    KMP(s1, lt, s2, lp);
    for(int i = 0; i < lp; i ++)
        cout<< d[i] <<" ";
    return 0;
}