Pagini recente » Cod sursa (job #236576) | Borderou de evaluare (job #1514584) | Borderou de evaluare (job #1540881) | Monitorul de evaluare | Cod sursa (job #993128)
Cod sursa(job #993128)
#include<cstdio>
#include<cstring>
using namespace std;
int sol,n,m,R,poz,i,Z[4000009],r[1013];
char A[2000009],B[2000009];
int min(int a,int b){if(a<b) return a;return b;}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A+1);n=strlen(A+1);
gets(B+1);m=strlen(B+1);
for(i=n+1;i<=n+m;i++)
A[i]=B[i-n];
Z[1]=0;
for(i=2;i<=n+m;i++)
{
Z[i]=0;
if(R>=i) Z[i]=min(Z[i-poz+1],R-i+1);
while(A[i+Z[i]]==A[Z[i]+1]&&Z[i]+i<=n+m) Z[i]++;
if(Z[i]+i-1>R)
{
R=Z[i]+i-1;
poz=i;
}
}
for(i=n+1;i<=n+m;i++)
if(Z[i]>=n)
{
sol++;
if(sol<=1000)
r[sol]=i-n;
}
printf("%d\n",sol);
for(i=1;i<=min(1000,sol);i++)
printf("%d ",r[i]-1);
return 0;
}