Cod sursa(job #1361546)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 25 februarie 2015 22:07:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

ifstream is("strmatch.in");
ofstream os("strmatch.out");

char A[2000002], B[2000002];
int N, M, k;
int PI[2000002];
int F;

vector <int> Sol;

void BuildPI()
{
    k = 0;
    for ( int 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;
    }
}

void MainEvent()
{
    k = 0;
    for ( int 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 )
            Sol.push_back(i-N);
    }
}

int main()
{
    is >> A+1 >> B+1;
    N = strlen(A+1);
    M = strlen(B+1);

    BuildPI();
    MainEvent();

    os << Sol.size() << '\n';
    F = min((int)Sol.size(),1000);
    for ( int i = 0; i < F; ++i )
        os << Sol[i] << " ";

}