Cod sursa(job #329328)

Utilizator aladinaladin aladinn aladin Data 5 iulie 2009 21:14:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
   #include <cstdio>  
   #include <cstring> 
   #define NMAX 2000002   
    char A[NMAX],B[NMAX];  
    long pi[NMAX],n,k,m,i,nr=0,x=0,sol[1001];   
   
   int main()  
   {  
     
       freopen("strmatch.in","r",stdin);  
       freopen("strmatch.out","w",stdout);  
        
       scanf("%s\n%s",A,B);     
       n=strlen(A);m=strlen(B);  
     
       k=0;pi[1]=0;          
       for (i=2;i<=n;i++)  
           {  
               for (;k&&(A[i-1]!=A[k]);)  
                   k=pi[k];  
                 
               if (A[i-1]==A[k]) k++;  
               pi[i]=k;  
           }  
       k=0;  
       for (i=1;i<=m;i++)  
           {  
               for (;k&&(B[i-1]!=A[k]);) k=pi[k];  
     
               if (B[i-1]==A[k]) k++;  
                 
               if (k==n) {if (nr<1000) {++nr;sol[nr]=i-n;} else x++;}   
           }  
       printf("%d\n",nr+x);  
       for (i=1;i<=nr;i++)  
           printf("%d ",sol[i]); 
       return 0;  
   }