Cod sursa(job #2730707)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 26 martie 2021 18:31:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "strmatch.in" );
ofstream g ( "strmatch.out" );
const int NMAX = 2000002;
char A[NMAX], B[NMAX];
int m, n, p[NMAX], sol[1001], nr;
void prefix()
{
    int k = 0;
    p[1] = 0;

    for ( int i = 2; i <= m; i++ )
    {
        while ( k > 0 && A[i] != A[k + 1] )
            k = p[k];

        if ( A[i] == A[k + 1] )
            k++;

        p[i] = k;
    }
}
void KMP()
{
    int k = 0;

    for ( int i = 1; i <= n; i++ )
    {
        while ( k > 0 && A[k + 1] != B[i] )
            k = p[k];

        if ( A[k + 1] == B[i] )
            k++;

        if ( k == m )
        {
            nr++;

            if ( nr <= 1000 )
                sol[nr] = i - m;

            k = p[k];
        }
    }
}
int main()
{
    f.getline ( A + 1, NMAX );
    m = f.gcount() - 1;
    f.getline ( B + 1, NMAX );
    n = f.gcount() - 1;
    prefix();
    KMP();
    g << nr << '\n';

    if ( nr >= 1000 )
        nr = 1000;

    for ( int i = 1; i <= nr; i++ )
        g << sol[i] << ' ';

    return 0;
}