Cod sursa(job #559354)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 17 martie 2011 19:43:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <algorithm>
#include <cstring>
#include <fstream>
#include <vector>

using namespace std;

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

const int Dim = 2000001;

char A[Dim], B[Dim];
int N, M, XXX, Pi[Dim];
vector <int> sol;

void GetPi() {

    int i, k;

    k = 0;
    Pi[1] = 0;
    for( i = 2; i <= N; ++i ) {

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

void KMP() {

    int i, q;

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

        while( q > 0 && A[q] != B[i - 1] )
            q = Pi[q];
        if( A[q] == B[i - 1] )
            ++q;
        if( q == N )
            if( ++XXX <= 1000 )
                sol.push_back( i - N );
    }
}

int main() {

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

    vector <int> :: iterator it;

    fin.getline( A, Dim );
    fin.getline( B, Dim );
    N = strlen( A );
    M = strlen( B );

    GetPi();
    KMP();

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

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

    return 0;
}