Cod sursa(job #993128)

Utilizator geniucosOncescu Costin geniucos Data 3 septembrie 2013 12:35:57
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#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;
}