Cod sursa(job #2863059)

Utilizator Y.MalmsteenB.P.M. Y.Malmsteen Data 6 martie 2022 12:15:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
//#include <iostream>
#include <fstream>

using namespace std;
const int NMAX = 2000002;

char A[NMAX], B[NMAX];
int m, n,
    p[NMAX],
    sol[1001], nr;

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

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 && B[i] != A[k + 1])
            k = p[k];
        if(B[i] == A[k + 1])
            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;
    //cout << m << ' ' << n << '\n';
    prefix();
    KMP();
    g << nr << '\n';
    if(nr >= 1000) nr = 1000;
    for(int i = 1; i <= nr; i++)
        g << sol[i] << ' ';
    return 0;
}