Cod sursa(job #459808)

Utilizator BitOneSAlexandru BitOne Data 31 mai 2010 11:57:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <string>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define Nmax 2000111

/*
 *
 */
 using namespace std;
 int Fprefix[Nmax];
 vector< int > r;
 string pattern, s;
 void Fp( int M )
 {
     int i, j;
     for( i=2; i <= M; ++i )
     {
         for( j=Fprefix[i-1]; j && pattern[i-1] != pattern[j] ; j=Fprefix[j] );
         if( pattern[i-1] == pattern[j] )
             ++j;
         Fprefix[i]=j;
     }
 }
 void KMP( int N, int M )
 {
     int i, j;
     Fp( M );
     for( i=j=0; j < N; )
     {
         if( pattern[i] == s[j] )
         {
             ++i, ++j;
             if( M == i )
                r.push_back( j-M );
         }
         else if( i )
                i=Fprefix[i];
              else ++j;
     }
 }
 int main( void )
 {
     ifstream in( "strmatch.in" );
     getline( in, pattern, '\n' );
     getline( in, s );
     KMP( s.size(), pattern.size() );
     ofstream out( "strmatch.out" );
     out<<r.size()<<'\n';
     copy( r.begin(), r.begin() + ( 1000 <= r.size() ? 1000 : r.size() ), ostream_iterator< int >( out, " " ) );
     return EXIT_SUCCESS;
 }