Cod sursa(job #2122879)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 5 februarie 2018 16:44:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 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;
    }
}

void KMP(char A[], char B[])
{
    int m = strlen(A+1);
    int n = strlen(B+1);


    for ( int i=1; i<=n; i++ )
        if ( B[i] == A[state[i-1]+1] )
            state[i] = state[i-1]+1;
        else
        {
            int k = prefix[state[i-1]];
            while ( k>0 && B[i] != A[k+1] ) k = prefix[k];
            state[i] = k+1;
        }
}

int out = 0;
vector<int> output;

void KMP_YT(char P[], char T[])
{
    int n = strlen(T+1);
    int m = strlen(P+1);
    int i = 1;
    int j = 1;
    int k = 1;


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

        if ( j > 1 ) j = prefix[j-1] + 1;
    }
}


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_YT(A, B);

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