Cod sursa(job #3311533)

Utilizator EduardoDinutaDinuta Eduard Stefan EduardoDinuta Data 22 septembrie 2025 22:31:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");

int main() {
    std::string A, B;

    in >> A >> B;
    int n = A.length(), m = B.length();

    std::vector<int> pos(n, -1);

    int j = - 1;

    for (int i = 1; i < n; i++) {
        while (A[i] != A[j + 1] && j != -1) j = pos[j];

        if (A[i] == A[j + 1]) j++;

        pos[i] = j;
    }

    std::vector<int> ans;
    j = -1;

    for (int i = 0; i < m; i++) {
        while (B[i] != A[j + 1] && j != -1) j = pos[j];

        if (B[i] == A[j + 1]) {
            j++;
        }

        if (j == n - 1) {
            ans.push_back(i - n + 1);
        }
    }

    out << ans.size() << '\n';

    for (int i = 0; i < std::min(int(ans.size()), 1000); i++) {
        out << ans[i] << " ";
    }
}