Cod sursa(job #3199475)

Utilizator raresgherasaRares Gherasa raresgherasa Data 1 februarie 2024 17:29:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NM = 2e6 + 5;
const int mod = 666013;

int p[NM];
int hs, ht[NM], inv[NM];
string s, t;
int n, m;

int pw (int a, int b) {
    int p = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            p = 1LL * p * a % mod;
        }
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return p;
}

int main() {
    fin >> s >> t;
    n = (int)s.size();
    m = (int)t.size();
    if (n > m) {
        fout << 0;
        return 0;
    }
    p[0] = 1;
    inv[0] = pw(p[0], mod - 2);
    for (int i = 1; i < NM; i++) {
        p[i] = 1LL * p[i - 1] * 31 % mod;
        inv[i] = pw(p[i], mod - 2);
    }
    for (int i = 0; i < n; i++) {
        hs = (hs + 1LL * p[i + 1] * (s[i] - 'A' + 1) % mod) % mod;
    }
    for (int i = 0; i < m; i++) {
        ht[i + 1] = (ht[i] + 1LL * p[i + 1] * (t[i] - 'A' + 1) % mod) % mod;
    }
    vector<int>pos;
    for (int i = n; i <= m; i++) {
        int Q = 1LL * (ht[i] - ht[i - n] + mod) % mod * inv[i - n] % mod;
        if (hs == Q) {
            pos.push_back(i - n);
        }
    }
    fout << (int)pos.size() << '\n';
    for (int i = 0; i < min(1000, (int)pos.size()); i++) {
        fout << pos[i] << " ";
    }
}