Cod sursa(job #2844061)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 3 februarie 2022 18:14:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>


using namespace std;
const long long NR = 2e6 + 100;

string a, b;
int p[NR];

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

signed main() {

    in >> a >> b;
    int l = 0;
    for (int i = 1; i < a.size(); ++i) {
        if (a[i] == a[l]) {
            ++l;
        } else {
            l = p[l];
        }
        p[i] = l;
    }
    l = 0;
    vector<int> sol;
    for (int i = 0; i < b.size(); ++i) {
        while (a[l] != b[i] && l) {
            l = p[l - 1];
        }
        if (b[i] == a[l]) {
            ++l;
        }
        if (l == a.size()) {
            sol.push_back(i - l + 1);
            l = p[l - 1];
        }
    }
    out << min(1000, (int) sol.size()) << '\n';
    for (int i = 0; i < min(1000, (int) sol.size()); ++i)
        cout << sol[i] << ' ';


    return 0;

}