Cod sursa(job #3361019)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 18 iulie 2026 16:59:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string a, b;
    std::cin >> a >> b;

    std::vector<int>pi(a.size(), 0);
    for (int i = 1; i < (int)a.size(); i++) {
        int j = pi[i - 1];
        while (j > 0 && a[i] != a[j]) {
            j = pi[j - 1];
        }
        if (a[i] == a[j]) {
            j++;
        }
        pi[i] = j;
    }

    int j = 0;

    int cnt_ = 0;
    std::vector<int>sol;
    for (int i = 0; i < (int)b.size(); i++) {
        while (j > 0 && b[i] != a[j]) {
            j = pi[j - 1];
        }
        if (b[i] == a[j]) {
            j++;
        }
        if (j == (int)a.size()) {
            if (++cnt_ <= 1000) {
                sol.push_back(i - (int)a.size());
            }
            j = pi[j - 1];
        }
    }
    std::cout << sol.size() << '\n';
    for (auto &c : sol)
    {
        std::cout << c + 1 << ' ';
    }
}