Cod sursa(job #3272417)

Utilizator labmoisil30Marius Darius labmoisil30 Data 29 ianuarie 2025 12:27:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

const int NMAX = 2e6+5;

int pi[NMAX];
string A, B, X;
vector<int> pozitii;

int main()
{
    fin >> A >> B;
    X = A+'#'+B;
    pi[0] = 0;
    int n = X.size(), j = 0;
    for (int i = 1; i < n; i++)
    {
        while (j > 0 && X[j] != X[i])
            j = pi[j-1];
        if (X[j] == X[i])
            j++;
        pi[i] = j;
        if (pi[i] == A.size())
            pozitii.push_back(i-2*A.size());
    }
    fout << pozitii.size() << nl;
    for (int i = 0; i < min(1000, (int)pozitii.size()); i++)
        fout << pozitii[i] << ' ';
    return 0;
}