Cod sursa(job #3274568)

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

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, 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;
    m = a.size();

    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] == m) rasp.push_back(i - m + 1 - (m + 1));
    }

    fout << rasp.size() << "\n";    

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

    return 0;
}