Cod sursa(job #160328)

Utilizator vrajalaMihai Viteazu, razboinicu luminii vrajala Data 15 martie 2008 00:31:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <string.h>

#define Lmax 2000002

char A[Lmax],B[Lmax];
int L1,L2,i;
int T[Lmax],P[1001],nr;

void citire()
{
 freopen("strmatch.in","r",stdin);
 scanf("%s",&A);
 scanf("%s",&B);
 L1=strlen(A);
 L2=strlen(B);
}

void prefix()
{
 int k,i;
 k=-1;
 T[0]=-1;
for (i=1;i<L1;++i)
     {
      while (k>-1 && A[k+1]!=A[i])
            k=T[k];
      if (A[k+1]==A[i]) ++k;
      T[i]=k;            
     }
}

void match()
{
 int k,i;
 k=-1;
 for (i=0;i<L2;++i)
     {
      while (k>-1 && A[k+1] != B[i])
            k=T[k];
     if (A[k+1]==B[i]) ++k;
     if (k==L1-1) 
        {
         P[++nr]=i-L1+1;
         if (nr==1000) return;
        }
     }
}

int main()
{
 citire();
 prefix();
 match();
 freopen("strmatch.out","w",stdout);
 printf("%d\n",nr);
 for (i=1;i<=nr;++i)
     printf("%d ",P[i]);
 fclose(stdout);    
 return 0;
}