Cod sursa(job #269049)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 2 martie 2009 11:42:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <string.h>

char A[2000001],B[2000001];
int p[2000000],sol[1001],nr;

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

scanf("%s\n",A+1);
scanf("%s",B+1);
int n,m,i;
n = strlen(A)-1;
//for (i=n;i>=0;i--) A[i] = A[i-1];
m = strlen(B)-1;
//for (i=m;i>=0;i--) B[i] = B[i-1];


p[1]=0;
int k=0;
for (i=2;i<=n;i++)
{
while (k>0 && A[k+1]!=A[i]) k=p[k];
if (A[k+1]==A[i]) k++;
p[i] = k;
}

k=0;
for (i=1;i<=m;i++)
{
while (k>0 && A[k+1]!=B[i]) k=p[k];
if (A[k+1]==B[i]) k++;
if (k==n)
        {
        nr++;
        if (nr<=1000) sol[nr] = i-n;
        k = p[k];
        }
}
printf("%d\n",nr);
if (nr>1000) nr = 1000;
for (i=1;i<=nr;i++) printf("%d ",sol[i]);
}