Cod sursa(job #2738677)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 6 aprilie 2021 11:00:29
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;
void DAU(const string &task = "") {
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
        freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PLEC() {
    exit(0);
}
const int N(6e6 + 6);
inline void LSP(char *s, int* lsp) {
    int j(0);
    lsp[0] = 0;
    for (size_t i = 1; i < strlen(s); ++i) {
        while (j > 0 && s[i] != s[j])
            j = lsp[j - 1];
        if (s[i] == s[j])
            ++j;
        lsp[i] = j;
    }
}
int lsp[N];
inline void KMP(char *text, char *pat) {
    int i(0), j(0), nt(static_cast<int>(strlen(text))), np(static_cast<int>(strlen(pat))), cnt(0);
    vector<int> res;
    LSP(pat, lsp);
    while (i < nt) {
        if (text[i] == pat[j])
            ++i, ++j;
        else {
            if (!j) ++i;
            else j = lsp[j - 1];
        }
        if (j == np) {
            ++cnt;
            if (cnt <= 1000)
                res.emplace_back(i - np);
            j = lsp[j - 1];
        }
    }
    cout << cnt << '\n';
    for (const int &x : res)
        cout << x << ' ';
}
char a[N], b[N];
signed main() {
    DAU("strmatch");
    cin >> a >> b;
    KMP(b, a);
    PLEC();
}