Cod sursa(job #1567464)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 13 ianuarie 2016 12:21:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <cstring>

const int DIM = 1 << 21;
using namespace std;

int Answer[DIM], cnt_answer;
int Prefix[DIM], N, M, length;
char Pattern[DIM], String[DIM];

int main () {

   freopen( "strmatch.in" , "r", stdin  );
   freopen( "strmatch.out", "w", stdout );

   scanf( "%s", Pattern + 1 ); N = strlen( Pattern + 1 );
   scanf( "%s", String  + 1 ); M = strlen( String  + 1 );

   length = 0;
   for( int i = 2; i <= N; i ++ ) {

      while( length && Pattern[i] != Pattern[length + 1] )
         length = Prefix[length];
      if( Pattern[i] == Pattern[length + 1] )
         length ++;

      Prefix[i] = length;
   }

   length = 0;
   for( int i = 1; i <= M; i ++ ) {

      while( length && String[i] != Pattern[length + 1] )
         length = Prefix[length];
      if( String[i] == Pattern[length + 1] )
         length ++;

      if( length == N ) {
         if( cnt_answer < 1000 )
            Answer[++cnt_answer] = i - length;
         else
            cnt_answer ++;
         length = Prefix[length];
      }
   }

   printf( "%d\n", cnt_answer );
   for( int i = 1; i <= cnt_answer && i <= 1000; i ++ )
      printf( "%d ", Answer[i] );

   return 0;
}