Cod sursa(job #3274562)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 7 februarie 2025 10:12:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, i, j, lung[4000002];
vector<int> rasp;
string a, b;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    fin >> a >> b;

    b = a + "@" + b;
    n = b.size();

    j = 0;
    for(i = 1; i < n; i++) {
        while(0 < j && b[j] != b[i]) j = lung[j - 1];
        if(b[j] == b[i]) j++;
        lung[i] = j;

        if(lung[i] == a.size()) rasp.push_back(i - a.size() + 1);
    }

    int nrMax = min((int)rasp.size(), 1000);
    fout << nrMax << "\n";
    for(i = 0; i < nrMax; i++) {
        fout << rasp[i] - (a.size() + 1) << " ";
    }

    return 0;
}