Cod sursa(job #3184384)

Utilizator susanSusan Ssssss susan Data 15 decembrie 2023 18:23:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>

using namespace std;

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

typedef long long ll;
const ll P = 1007, MOD = 1e9 + 7;

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

    if (a.size() > b.size()) {
        g << "0\n";
        exit(0);
    }

    vector<ll> h(b.size() + 1), putere(b.size() + 1);

    vector<int> rez;
    rez.reserve(1000);

    putere[0] = 1;
    for (int i = 0; i < b.size(); ++i) {
        putere[i + 1] = (putere[i] * P) % MOD;
        h[i + 1] = (h[i] + (b[i] + 1) * putere[i]) % MOD;
    }

    ll hashul = 0, cnt = 0;
    for (int i = 0; i < a.size(); ++i)
        hashul = (hashul + (a[i] + 1) * putere[i]) % MOD;

    for (int i = 0; i + a.size() - 1 < b.size(); ++i) {
        ll curr = (h[i + a.size()] + MOD - h[i]) % MOD;

        if (curr == (hashul * putere[i]) % MOD) {
            ++cnt;
            if (rez.size() < 1000)
                rez.emplace_back(i);
        }
    }

    g << cnt << "\n";
    for (auto it: rez)
        g << it << " ";
    g << "\n";
}