Cod sursa(job #2716472)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 5 martie 2021 11:21:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int LMAX = 2e6;

char a[LMAX + 2], b[LMAX + 2];
int pi[LMAX + 1];
vector<int> ans;

int main() {
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    int n, m;
    in >> (a + 1) >> (b + 1);
    m = strlen(a + 1), n = strlen(b + 1);

    int lung;
    pi[1] = lung = 0;
    for (int i = 2; i <= m; ++i) {
        while (lung > 0 && a[i] != a[lung + 1])
            lung = pi[lung];
        if (a[i] == a[lung + 1])
            ++lung;
        pi[i] = lung;
    }

    lung = 0;
    for (int i = 1; i <= n; ++i) {
        while (lung > 0 && b[i] != a[lung + 1])
            lung = pi[lung];
        if (b[i] == a[lung + 1])
            ++lung;
        if (lung == m)
            ans.push_back(i - lung);
    }
    if (ans.size() > 1000) {
        out << "1000\n";
        for (int i = 0; i < 1000; ++i)
            out << ans[i] << ' ';
    }
    else {
        out << ans.size() << '\n';
        for (auto i : ans)
            out << i << ' ';
    }

    in.close();
    out.close();
}