Pagini recente » Statistici Raduna Daniel Florin (daniraduna) | Statistici Petru Rares (PetruRares) | Statistici Supuran Marius (mar19) | Cod sursa (job #1057044) | Cod sursa (job #1552503)
#include <cstdio>
#define NMAX 2000000
#include <algorithm>
#include <cstring>
using namespace std;
char A[NMAX+10],B[NMAX+10];
int n,m,i,phi[NMAX+10],phi2[NMAX+10],sol,k;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A+1);
gets(B+1);
n=strlen(A+1);
m=strlen(B+1);
phi[1]=0;
for(i=2; i<=n; ++i)
{
k=phi[i-1];
while(k && A[i]!=A[k+1])
k=phi[k];
if(A[i]==A[k+1])
phi[i]=k+1;
else phi[i]=0;
}
phi2[1]=0;
for(i=2; i<=m; ++i)
{
k=phi2[i-1];
while(k && B[i]!=A[k+1])
k=phi2[k];
if(B[i]==A[k+1])
phi2[i]=k+1;
else phi2[i]=0;
if(phi2[i]==n)
++sol;
}
printf("%d\n",sol);
sol=min(sol,1000);
for(i=1; i<=m && sol; ++i)
if(phi2[i]==n)
{
printf("%d ",i-n);
--sol;
}
return 0;
}