Cod sursa(job #415796)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 11 martie 2010 20:54:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
# include <algorithm>
# include <fstream>
# include <string>
# include <vector>

using namespace std;

# define Max_N 2000005

const char Input[] = "kmp.in";
const char Output[] = "kmp.out";

int N, M, Nr_sol;
int pi[ Max_N ];
string A, B;
vector <int> sol;

void calc_pi() {

    int i, k;

    k = 0;
    pi[ 1 ] = 0;

    for( i = 2; i <= N; ++i ) {

        while( k > 0 && A[ k+1 ] != A[ i ] )
            k = pi[ k ];
        if( A[ k+1 ] == A[ i ] )
            ++k;

        pi[ i ] = k;
    }
}

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i, k;
    vector <int> :: iterator it;

    fin >> A >> B;

    N = A.length();
    M = B.length();

    A.insert( 0, "X" );
    B.insert( 0, "X" );

    k = 0;
    calc_pi();

    for( i = 1; i <= M; ++i ) {

        while( k > 0 && A[ k+1 ] != B[ i ] )
            k = pi[ k ];
        if( A[ k+1 ] == B[ i ] )
            ++k;

        if( k == N ) {

            k = pi[ k ];

            ++Nr_sol;
            sol.push_back( i-N );
        }
    }

    fout << Nr_sol << "\n";
    for( it = sol.begin(); it != sol.end(); ++it )
        fout << *it << " ";

    fin.close();
    fout.close();

    return 0;
}