Cod sursa(job #995323)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 8 septembrie 2013 16:53:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int Lmax = 2000002;

int L[Lmax];
char Pattern[Lmax], Text[Lmax];
vector <int> match;

int P, T;

void read()
{
    ifstream f("strmatch.in");

    f >> ( Pattern + 1 );
    f >> ( Text + 1 );

    Pattern[0] = ' ';
    Text[0] = ' ';

    P = strlen ( Pattern ) - 1;
    T = strlen ( Text ) - 1;

    f.close();
}

void prefix()
{
    L[1] = 0;
    int k = 0;

    for ( int p = 2; p <= P; ++p )
    {
        while ( k > 0 && Pattern[k + 1] != Pattern[p] )
                k = L[k];

        if ( Pattern[k + 1] == Pattern[p] )
                k++;

        L[p] = k;
    }
}

void KMP()
{
    int k = 0;

    for ( int t = 1; t <= T; ++t )
    {
        while ( k > 0 && Pattern[k + 1] != Text[t] )
                k = L[k];

        if ( Pattern[k + 1] == Text[t] )
                k++;

        if ( k == P )
        {
            if ( match.size() < 1000 )
                match.push_back( t - P );

            k = L[k];
        }
    }
}

void print()
{
    ofstream g("strmatch.out");

    g << match.size() << "\n";

    for ( unsigned i = 0; i < match.size(); ++i )
            g << match[i] << " ";

    g << "\n";

    g.close();
}

int main()
{
    read();
    prefix();
    KMP();
    print();

    return 0;
}