Pagini recente » Cod sursa (job #879860) | Cod sursa (job #2304963) | Cod sursa (job #422047) | Cod sursa (job #3182149) | Cod sursa (job #1207491)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define NMAX 2000004
int n,m,r,q,st[1005],p[NMAX+1];
char A[NMAX+1],B[NMAX+1];
void prefix()
{
int i;
q=0;
for (i=2;i<=n;++i)
{
while (A[i]!=A[q+1] && q>0)
q=p[q];
if (A[i]==A[q+1])
++q;
p[i]=q;
}
}
int main()
{
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin.getline(A+1,NMAX);
cin.getline(B+1,NMAX);
n=strlen(A+1), m=strlen(B+1);
prefix();
q=0;
for (i=1;i<=m;++i)
{
while (B[i]!=A[q+1] && q>0)
q=p[q];
if (B[i]==A[q+1])
++q;
if (q==n)
{
++r;
if (r<1001) st[r]=i-n;
q=p[q];
}
}
printf("%d\n",r);
r=min(r,1000);
for (i=1;i<=r;++i)
printf("%d ",st[i]);
printf("\n");
return 0;
}