Cod sursa(job #2716469)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 5 martie 2021 11:18:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 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);
    }
    out << ans.size() << '\n';
    for (auto i : ans)
        out << i << ' ';

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