Cod sursa(job #3367959)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 12 octombrie 2026 15:36:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

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

int main() {
    string a, b;
    in >> b >> a;

    int n = a.length();
    int m = b.length();

    std::vector<int> dp(m + 1, -1);

    int j = -1;

    for (int i = 1; i < m; i++) {
        while (j >= 0 && b[i] != b[j + 1]) j = dp[j];

        if (b[i] == b[j + 1])
            j++;
        
        dp[i] = j;
    }

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

    for (int i = 0; i < n; i++) {
        while (j >= 0 && a[i] != b[j + 1]) j = dp[j];

        if (a[i] == b[j + 1])
            j++;

        if (j == m - 1) {
            cnt++;
            if (ans.size() < 1000) {
                ans.push_back(i - m + 1);
            }

            j = dp[j];
        }
    }

    out << cnt << '\n';
    for (auto it : ans) {
        out << it << ' ';
    }
}