Cod sursa(job #3345138)

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

#define NMAX 2000005
#define CNTMAX 1005

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

    std::cin >> p >> t;

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

    delta[0] = 0;

    for (int i = 1, j = 0; i < m;) {
        if (p[i] == p[j]) {
            delta[i] = j + 1;

            ++i;
            ++j;
        } else {
            if (j == 0) {
                delta[i] = 0; // -1 + 1

                ++i;
            } else {
                j = delta[j - 1];
            }
        }
    }

    for (int i = 0, j = 0; i < n;) {
        if (t[i] == p[j]) {
            ++i;
            ++j;

            if (j == m) {
                if (cnt < CNTMAX)
                    pos[cnt] = i - m;

                ++cnt;

                j = delta[j - 1];
            }
        } else {
            if (j == 0)
                ++i;
            else
                j = delta[j - 1];
        }
    }

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

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

    std::cout << '\n';

    return 0;
}