Cod sursa(job #2122886)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 5 februarie 2018 16:51:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>


using namespace std;
ifstream f("strmatch.in" );
ofstream g("strmatch.out");

int state[2000004], prefix[2000004];
char A[2000004], B[2000004];


void InitializareAutomat(char A[])
{
    int m = strlen(A+1);
    prefix[1] = 0;
    int i = 0;

    for ( int j=2; j<=m; j++ )
    {
        while ( i>0 && A[i+1] != A[j] )
            i = prefix[i];
        if ( A[i+1] == A[j] ) i++;
        prefix[j] = i;
    }
}


int out = 0;
vector<int> output;

void KMP(char P[], char T[])
{
    int m = strlen(P+1);
    int n = strlen(T+1);
    int k = 0;

    for ( int i=1; i<=n; i++ )
    {
        if ( B[i] == A[k+1] )
            k++;
        else
        {
            while ( k>0 && B[i] != A[k+1] ) k = prefix[k];
            if ( T[i] == P[k+1] ) k++;
        }
        if ( k == m ) {
            out++;
            output.push_back(i-k);
        }
    }
}


int main()
{
    f.getline(A+1, 2000004);
    f.getline(B+1, 2000004);

    int m = strlen(A+1);
    int n = strlen(B+1);

    InitializareAutomat(A);
    KMP(A, B);


    g << out << '\n';
    for ( int i=0; i<min(unsigned(1000), output.size()); i++ )
        g << output[i] << ' ';
}