Pagini recente » Cod sursa (job #1168580) | Cod sursa (job #617146) | Monitorul de evaluare | Cod sursa (job #150200) | Cod sursa (job #1049890)
#include <stdio.h>
#include <cstring>
using namespace std;
const int strLEN=2000002;
char A[strLEN],B[strLEN];
int lps[strLEN-2];
int sol[strLEN-1];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,strLEN,stdin);
fgets(B,strLEN,stdin);
int nA=strlen(A)-1;
int nB=strlen(B)-1;
//longest prefix-suffix
memset(lps,-1,sizeof(lps));
int pos=-1;
for(int i=1;i<nA;++i)
{
while(pos>=0&&A[pos+1]!=A[i]) pos=lps[pos];
if(A[pos+1]==A[i])
if(pos>=0) lps[i]=lps[pos]+1;
else lps[i]=0;
}
pos=-1;
int length=0;
for(int i=0;i<nB;++i)
{
while(pos>=0&&B[i]!=A[pos+1]) pos=lps[pos];
if(B[i]==A[pos+1])
{
++length;
++pos;
if(length==nA)
{
sol[++sol[0]]=i-length+1;
length=lps[pos]+1;
pos=lps[pos];
}
}
else
if(pos>=0) length=lps[pos]+1;
else length=0;
}
printf("%d\n",sol[0]);
for(int i=1;i<=sol[0]&&i<=1000;++i)
printf("%d ",sol[i]);
printf("\n");
return 0;
}