Cod sursa(job #3329494)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 13 decembrie 2025 15:20:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
/// https://www.infoarena.ro/automate-finite-si-kmp
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int NMAX = 2e6 + 2;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[NMAX], b[NMAX];
int n, m, pi[NMAX], sol;
vector<int> vsol;

void calcPrefix()
{
    int x = -1;
    pi[0] = -1;
    for(int i = 1; i < n; ++i)
    {
        while(x >= 0 && a[x + 1] != a[i])
            x = pi[x];
        if(a[x + 1] == a[i])
            ++x;
        pi[i] = x;
    }
}

void potrivireKMP()
{
    int x = -1;
    for(int i = 0; i < m; ++i)
    {
        while(x >= 0 && a[x + 1] != b[i])
            x = pi[x];
        if(a[x + 1] == b[i])
            ++x;
        if(x == n - 1) /// Potrivire
        {
            if(++sol <= 1000)
                vsol.push_back(i - n + 1);
            x = pi[x];
        }
    }
}

int main()
{
    fin >> a >> b;
    n = strlen(a), m = strlen(b);
    calcPrefix();
    potrivireKMP();
    fout << sol << "\n";
    for(const auto& x : vsol) fout << x << " ";
    return 0;
}