kmp

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;

const int N=1e6+10;

char s1[N],s2[N];
int d[N];//d[i]表示以i结尾的字符串中 最大公共前后缀的长度 
vector<int> v;

void init()//得到模式串的d[] 下标是从0开始的 
{
    int len=strlen(s2);
    int i=1,j=0;//两个s2串 
    while(i<len)
    {
        if(s2[i]==s2[j])
        d[i++]=++j;
        else {
            if(j>0) j=d[j-1];
            else i++;
        }
    }
}

void kmp()
{
    int i=0,j=0;
    int len=strlen(s1),ns2=strlen(s2);
    while(i<len)
    {
        if(s1[i]==s2[j])
        {
            i++,j++;
            if(j==ns2)//成功找到 
            {
                j=d[j-1];//继续找完所有匹配的子串 
                v.push_back(i-ns2);//s1与s2完全匹配的字串的最左边 
            }
        }
        else {
            if(j>0) j=d[j-1];
            else i++;
        }
    }
}

int main()
{
    scanf("%s%s",s1,s2);
    
    init();
    
    kmp();
    
    for(int x:v) printf("%d\n",x+1);
    int ns2=strlen(s2);
    for(int i=0;i<ns2;i++)
    printf("%d ",d[i]);
    
    return 0;
}