Cod sursa(job #613185)

Utilizator BitOneSAlexandru BitOne Data 17 septembrie 2011 20:58:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>


using namespace std;
string s, pattern;
vector< int > failF, ans;
int sSize, patternSize, ansSize;
void FailureFunction()
{
    int i, j;
    failF.push_back(0);
    failF.push_back(0);
    for( i=2; i <= patternSize; ++i )
    {
        for( j=failF[i-1]; j && pattern[i-1] != pattern[j]; j=failF[j] );
        if( pattern[i-1] == pattern[j] )
            ++j;
        failF.push_back(j);
    }
}
void KMP()
{
    int i, j;
    FailureFunction();
    pattern.push_back(' ');
    s.push_back(' ');
    for( i=j=0; i < sSize; )
    {
        if( s[i] == pattern[j] )
        {
            ++i, ++j;
            if( patternSize == j )
            {
                ++ansSize;
                if( 1000 >= ansSize )
                    ans.push_back( i-patternSize );
            }
        }
        else if( j )
                j=failF[j];
              else ++i;
    }
    pattern.erase( pattern.end()-1 );
    s.erase( s.end()-1 );
}
int main( void )
{
    ifstream in( "strmatch.in" );
    getline( in, pattern );
    getline( in, s );
    patternSize=pattern.size();
    sSize=s.size();
    KMP();
    ofstream out( "strmatch.out" );
    out<<ansSize<<'\n';
    copy( ans.begin(), ans.end(), ostream_iterator<int>( out, " " ) );
    out<<'\n';
    return EXIT_SUCCESS;
}