Cod sursa(job #3291633)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 5 aprilie 2025 11:03:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda cex_9 Marime 0.62 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() {
    fin >> a >> b;
    b = a + "#" + b;

    n = a.size();
    m = b.size();

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

        if(lung[i] == n) rasp.push_back(i - n);
    }

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

    rasp.resize(min(rasp.size(), 1000));
    for(int cur : rasp) fout << cur - n << " ";

    return 0;
}