Cod sursa(job #1376733)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 martie 2015 18:35:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>

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

using namespace std;

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

char Line1[NMAX] ,Line2[NMAX] ;
int pref[NMAX]  , N , M , Answer ;
vector < int > Sol;

void CreatePref ( void ){
    int i , j , q ;
    for ( i = 2 , q = 0 ; i <= N ; ++i ){
       while ( Line1[i] != Line1[q+1] and q   )
           q = pref[q];
      if( Line1[i] == Line1[q+1])
      ++q;
      pref[i] = q;
    }
}
void DoKMP ( void ){
    int i , j , q;
    CreatePref();
    for ( i = 1  , q = 0; i <= M ; ++i ){
       while( Line2[i] != Line1[q+1] and q )
         q = pref[q];
       if ( Line2[i] == Line1[q+1] )
       ++q;
       if ( q == N ){
          if ( Answer < 1000 ){
          q = pref[q];
          Sol.push_back ( i-N +1);
        }
        ++Answer;
       }
    }
}

int main ( void ) {
    int i , j ;
    Line1[0] = Line2[0] = ' ';
    in >> ( Line1+ 1 ) , N = strlen(Line1) , --N;
    in >> ( Line2 + 1 ) , M = strlen(Line2) , --M;
    DoKMP();
    out << Answer << "\n";
    for ( vector < int > ::iterator it = Sol.begin() ; it != Sol.end() ; ++it )
        out << *it - 1 << " ";
    in.close();
    out.close();
    return 0 ;
}