描述：
给出两个字符串 s1 和 s2 ，其中 s2 为 s1 的子串，求出 s2 在 s1 中所有出现的位置。同时要求输出 s2 的 fail 数组。
思路：
KMP模板。
标程：
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000001
char s1[maxn],s2[maxn];
int fail[maxn];
int ans[maxn],cnt;
int len1,len2,j=;
inline void get()
{
for(int i=;i<=len2;i++)
{
while(j&&s2[i]!=s2[j+]) j=fail[j];//不能继续匹配且j还没有减到0，考虑退一步
if(s2[i]==s2[j+]) j++;//能匹配，j的值+1
fail[i]=j;
}
}
inline void kmp()
{
j=;
for(int i=;i<=len1;i++)
{
while(j>&&s1[i]!=s2[j+]) j=fail[j];//不能继续匹配且j还没减到0，减小j的值
if(s1[i]==s2[j+]) j++;//能继续匹配j，j的值+1
if(j==len2)//找到一处匹配
{
ans[++cnt]=i-len2+;//记录位置
j=fail[j];//往后跳，继续找
}
}
}
int main()
{
scanf("%s",s1+);
scanf("%s",s2+);
len1=strlen(s1+);
len2=strlen(s2+);
get();
kmp();
for(int i=;i<=cnt;i++)
printf("%d\n",ans[i]);//输出s2在s1中出现的位置
for(int i=;i<=len2;i++)
printf("%d ",fail[i]);//输出fail数组
return ;
}