Cod sursa(job #156307)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 12 martie 2008 14:32:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
# include <stdio.h>
# include <string.h>

# define nmax 2000002
# define FIN "strmatch.in"
# define FOUT "strmatch.out"

char T[nmax],P[nmax];
int x,k,i,n,m,Next[nmax],ct,sol[1001];

int main()
{
 freopen(FIN,"r",stdin);
 freopen(FOUT,"w",stdout);
 scanf("%s",P+1); scanf("%s",T+1);
 m=strlen(P+1); n=strlen(T+1);
 Next[1]=0; k=0;
 for (i=2; i<=m; i++)
   {
    while (k>0 && P[k+1]!=P[i]) k=Next[k];
    if (P[k+1]==P[i]) k++;
    Next[i]=k;
   }
 x=0; ct=0;
 for (i=1; i<=n; i++)
   {
    while (x>0 && P[x+1]!=T[i]) x=Next[x];
    if (P[x+1]==T[i]) x++;
    if (x==m)
      {
       ct++;
       if (ct<=1000) sol[ct]=i-m;
       x=Next[x];
      }
   }
 printf("%ld\n",ct);
 if (ct>1000) ct=1000;
 for (i=1; i<=ct; i++)
   printf("%ld ",sol[i]);
 return 0;
}