设想有一条竖线代表大串当前匹配到的字符的右边，一格一格往后移，同时小串已经匹配的位置和竖线右对齐。
如果竖线右移一格之后大小串下一个字符不匹配，就把小串往后移，直接移到最长的公共前后缀前缀盖过后缀，直到下一格字符匹配或下一个字符是小串的头字符。
为什么要计算前后缀呢？
在下一个字符之前的已匹配串中，下一次完全匹配一定是前缀移到后缀位置
事实1.如果已匹配串中的字符各不相同，b串可以直接往后移k位，k为已匹配长度。
因为只要移动了一位就不可能匹配的上
ai,我还是太蒻了
#include<bits/stdc++.h>
using namespace std;
int ol[1000005]={0};
int main()
{
char s[1000005];
cin>>s+1;
char s1[1000005];
cin>>s1+1;
int j=0;
ol[1]=0;
for(int i=2;s1[i];i++)
{
while(j>0&&s1[i]!=s1[j+1]) j=ol[j];//找所有以s1[i-1]为结尾的公共前后缀
if(s1[i]==s1[j+1]) j++;
ol[i]=j;
}
j=0;
for(int i=1;s[i];i++)
{
while(j&&s1[j+1]!=s[i])j=ol[j];
if(s1[j+1]==s[i])j++;
if(j==strlen(s1+1))
{
printf("%d\n",i-j+1);
j=ol[j];
}
}
for(int i=1;s1[i];i++)printf("%d ",ol[i]);
return 0;
}