Cod sursa(job #3370655)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 26 octombrie 2026 17:40:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

vector<int> rabin_karp(string_view text, string_view pattern)
{
    int n = text.size();
    int m = pattern.size();

    if (n < m)
        return {};

    constexpr int P = 257;
    constexpr int MOD = 1e9 + 7;

    vector<long long> p_pow(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i - 1] * P) % MOD;

    vector<long long> h(n + 1);
    h[0] = 0;
    for (int i = 0; i < n; i++)
        h[i + 1] = (h[i] + text[i] * p_pow[i]) % MOD;

    long long h_p = 0;
    for (int i = 0; i < m; i++)
        h_p = (h_p + pattern[i] * p_pow[i]) % MOD;

    vector<int> indices;
    for (int i = 0; i + m - 1 < n; i++) {
        long long temp_h = (h[i + m] + MOD - h[i]) % MOD;
        if (temp_h == h_p * p_pow[i] % MOD) {
            indices.push_back(i);
            if (indices.size() == 1000)
                break;
        }
    }
    return indices;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    string text;
    string pattern;
    cin >> pattern >> text;

    vector<int> indices = rabin_karp(text, pattern);
    cout << indices.size() << '\n';
    for (int i : indices)
        cout << i << ' ';
    cout << '\n';

    return 0;
}