Cod sursa(job #3329495)

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

using namespace std;

const int NMAX = 2e6 + 1;

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 = 0;
    for(int i = 2; i <= n; ++i)
    {
        while(x > 0 && a[x] != a[i - 1])
            x = pi[x];
        if(a[x] == a[i - 1])
            ++x;
        pi[i] = x;
    }
}

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

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;
}