Cod sursa(job #1727792)

Utilizator TiiberiuBujor Tiberiu-Cosmin Tiiberiu Data 11 iulie 2016 16:37:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
 
using namespace std;
 
const int BIG = 2000005;
char sir_total[BIG],sir_comparat[BIG],KMP[BIG];
 
int main() {
     
    int n,m,k=0,cnt=0,j,index = 0;
    int poz[BIG],z=0;
     
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
     
   scanf("%s%s",sir_comparat+1,sir_total+1);
    
   n  = strlen(sir_total+1);
   m  = strlen(sir_comparat+1);
    
   if(n < m){
        printf("%d\n",0);
        fclose(stdin);
        fclose(stdout);
    } 
   for(int i=1;i<=n;){
       if(sir_comparat[i] == sir_comparat[index]){
           KMP[i] = index;
           index++;
           i++;}
       else{
           if(index)
               index = KMP[index-1];
           else{
               KMP[i] = 0;
               i++;
           }
       }
   }
   while(k < n){
       if(j == m){
           poz[z] = k-j;
           z++;
           j=0;    
       }   
       if(sir_total[k] == sir_comparat[j]){
           k++;
           j++;
       }
       else
           if(j)
               j = KMP[j-1];
           else
               k++;
       
       
   }
//   for(int i=1;i<=n;i++){
//    
//       if(sir_total[i] == sir_comparat[k]){ 
//           poz[z] = i-1;
//           k++;
//           for(j=i+1;k<=m;j++,k++)
//               if(sir_total[j] == sir_comparat[k])
//                   cnt++; 
//           if(cnt+1 == m)
//                z++;
//           cnt= 0;k=1;  
//       }
//   }
    printf("%d\n",z);
     z = min(z, 1000);
   for(int i=0;i<z;i++)
       printf("%d ",poz[i]);
    
    return 0;
        
}