Cod sursa(job #3345221)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 8 martie 2026 15:23:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstring>
#include <iostream>

#define NMAX 2000005
#define KMAX 1000

int main()
{
    int n, m, cnt = 0;
    char t[NMAX], p[NMAX];
    int delta[NMAX];
    int pos[KMAX];
    
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    std::cin >> p >> t;

    m = strlen(p);
    n = strlen(t);

    delta[0] = 0;

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

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

        delta[i] = j;
    }

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

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

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

            ++cnt;

            j = delta[j - 1];
        }
    }

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

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

    std::cout << '\n';

    return 0;
}