Cod sursa(job #329324)

Utilizator aladinaladin aladinn aladin Data 5 iulie 2009 21:02:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
   #include <cstdio>  
   #include <cstring> 
   #define NMAX 2000002   
    char A[NMAX],B[NMAX];  
    long pi[NMAX];  
    long n,k,m,i,nr=0;  
    long int 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;}    
           }  
       printf("%d\n",nr);  
       for (i=1;i<=nr;i++)  
           printf("%d ",sol[i]); 
       return 0;  
   }