Cod sursa(job #2959278)

Utilizator cristiWTCristi Tanase cristiWT Data 30 decembrie 2022 14:09:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int p = 53, mod = 1e9 + 7, NMAX = 2e6, d = 52;
string a, b;


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> a >> b;
    int n = (int) b.size(), m = (int) a.size(), pw = 1, ha = 0, hb = 0;
    for (int i = 0; i < m; i++) {
        ha = (ha * p + a[i]) % mod;
        if (i) pw = pw * p % mod;
        hb = (hb * p + b[i]) % mod;
    }

    vector<int> ans;
    if (ha == hb) ans.push_back(0);
    for (int i = m; i < n; i++) {
        hb = ((hb - b[i - m] * pw % mod + mod) % mod * p + b[i]) % mod;
        if (ha == hb) ans.push_back(i - m + 1);
    }

    cout << ans.size() << '\n';
    for (int i = 0; i < min((int) ans.size(), 1000LL); i++)
        cout << ans[i] << ' ';
}