Cod sursa(job #1320247)

Utilizator superman_01Avramescu Cristian superman_01 Data 17 ianuarie 2015 19:17:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 2000005
#define get_max(a,b) ((a)>(b)?(a):(b))

using namespace std;

ifstream in ( "strmatch.in" );
ofstream out ( "strmatch.out" );

char sir1[NMAX] , sir2[NMAX];
int N , M  , Answer , Sol[NMAX] ;
int pref[NMAX];

void KMP ( void ) {
   int i , j , q = 0 ;
      for ( i = 2 ; i <= N ; ++i ){
           while ( q and sir1[q+1]!= sir1[i] )
           q = pref[q];
           if ( sir1[q+1] == sir1[i])
             ++q;
            pref[i] = q ;
      }
    for ( i = 1 , q = 0 ; i <= M ; ++i ){
     while ( q and sir1[q+1]!= sir2[i])
     q = pref[q];
     if ( sir1[q+1] == sir2[i] )
     ++q;
     if ( q == N ){
        q = pref[q];
        ++Answer ;
        if ( Answer <= 1000 )
        Sol[Answer] = i - N ;
     }
    }
}

int main ( void ){
   int i , j ;
   sir1[0] = ' ' ,sir2[0] = ' ';
   in >> (sir1 +1) >> (sir2+1);
   N = strlen(sir1) - 1 ;
   M = strlen(sir2) - 1 ;
   KMP();
   out << Answer << "\n";
   for ( i = 1 ; i <= Answer ; ++i )
   out << Sol[i] << " ";
   in.close();
   out.close();
   return 0 ;
}