Cod sursa(job #3274560)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 7 februarie 2025 10:03:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 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(j == m) rasp.push_back((i - m + 1) - (m + 1));
    }

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

    return 0;
}