Cod sursa(job #3345126)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 8 martie 2026 00:22:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>

#define NMAX 2000005

int main() {
    int n, m, cnt = 0;
    std::string p, t;
    int pi[NMAX];
    int pos[1000];

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    std::cin >> p >> t;

    m = p.size();
    n = t.size();

    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];

        if (p[i] == p[j])
            ++j;

        pi[i] = j;
    }

    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && t[i] != p[j])
            j = pi[j - 1];

        if (t[i] == p[j])
            ++j;

        if (j == m) {
            if (cnt < 1000)
                pos[cnt++] = i - m + 1;

            j = pi[j - 1];
        }
    }

    std::cout << cnt << '\n';

    for (int i = 0; i < cnt; ++i)
        std::cout << pos[i] << ' ';

    std::cout << '\n';

    return 0;
}