题目链接：
http://acm.scu.edu.cn/soj/problem.action?id=4438
题解：
变形kmp
代码：
#include <cstdio>
#include <cstring>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define met(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn =
5*
1e6+
10;
char s1[maxn],s2[maxn];
char name[maxn];
int nextt[maxn];
int pre[maxn];
int k;
void kmp_pre(
char x[],
int m,
int next[])
{
int i,j;
j=next[
0]=-
1 ;
i=
0;
while(i <m)
{
while(-
1!=j && x[i]!=x[j])j=next[j];
next[++ i]=++ j;
}
}
void preKMP(
char x[],
int m,
int kmpNext[])
{
int i,j;
j=kmpNext[
0] =-
1; i=
0;
while(i<m)
{
while(-
1!=j && x[i]!=x[j])
j=kmpNext[j];
if(x[++ i]==x [++j] )
kmpNext[ i]=kmpNext [j];
else kmpNext[i]=j;
}
}
void KMP_Count(
char x[],
int m,
char y[],
int n)
{
int i,j;
met(name,
'\0');
met(pre,
0);
preKMP(x,m,nextt);
kmp_pre(x,m,nextt);
i=j=
0;
k=
0;
while(i<n)
{
name[k]=y[i++];
while(-
1!=j &&name[k]!=x[j])
j=nextt[j];
j++;
k++;
pre[k]=j;
if(j>=m)
{
k-=m;
j=pre[k];
}
}
}
int main()
{
while (
scanf(
"%s",s1)!=EOF)
{
scanf(
"%s",s2);
int len1=
strlen(s1);
int len2=
strlen(s2);
KMP_Count(s1,len1,s2,len2);
for(
int i=
0;i<k;i++)
printf(
"%c",name[i]);
printf(
"\n");
}
}
