Cod sursa(job #668923)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 25 ianuarie 2012 20:45:08
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
#include <string.h>
#define lmax 2000005
char A[lmax],B[lmax];
int n,m,urm[lmax],sol,poz[1005];
int main()
{ int i,k;
freopen("strmatch.in","r",stdin);
gets(A); gets(B); m=strlen(A); n=strlen(B);
fclose(stdin);
k=0; urm[1]=0;
for(i=1;i<m;++i)
    {
    while(k>0&&A[k]!=A[i])
        k=urm[k];
    if(A[k]==A[i])++k;
    urm[i+1]=k;
    }
k=0; sol=0;
for(i=1;i<n && sol<1001;++i)
    {
    while(k>0&&A[k]!=B[i])
        k=urm[k];
    if(A[k]==B[i])++k;
    if(k==m){
            sol++; poz[sol]=i-m+1; k=urm[k];
            }
    }
if(sol>1000)sol=1000;
freopen("strmatch.out","w",stdout);
printf("%d\n",sol);
for(i=1;i<=sol;++i)
    printf("%d ",poz[i]);
fclose(stdout);
return 0;
}