Cod sursa(job #668930)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 25 ianuarie 2012 21:02:26
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 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,x;
freopen("strmatch.in","r",stdin);
gets(A+1); gets(B+1);
A[0]=' '; B[0]=' ';
m=strlen(A)-1; n=strlen(B)-1;
fclose(stdin);
k=0; urm[1]=0;
for(i=2;i<=m;++i)
    {
    while(k>0&&A[k+1]!=A[i])
        k=urm[k];
    if(A[k+1]==A[i])++k;
    urm[i]=k;
    }
k=0; sol=0;
for(i=1;i<=n;++i)
    {
    while(k>0&&A[k+1]!=B[i])
        k=urm[k];
    if(A[k+1]==B[i])++k;
    if(k==m){
            sol++; poz[sol]=i-m; k=urm[k];
            }
    }
if(sol>1000)x=1000;
    else x=sol;
freopen("strmatch.out","w",stdout);
printf("%d\n",sol);
for(i=1;i<=x;++i)
    printf("%d ",poz[i]);
fclose(stdout);
return 0;
}