Cod sursa(job #3247074)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 5 octombrie 2024 15:29:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

using i64 = long long;
using pii = pair<int, int>;

const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int N = 2e6 + 5;


pii hash_pat, _hash_text[N], *hash_text;
int pow1, pow2, ans;
string pat, text;
vector<int> occurences;


int main() {
    fi >> pat >> text;

    hash_text = _hash_text + 1;

    occurences.reserve(1000);
    // calculam hash_pat
    for (int i = 0; i < pat.size(); ++i) {
        hash_pat.x = (i64(hash_pat.x) * 128 + pat[i]) % MOD1;
        hash_pat.y = (i64(hash_pat.y) * 128 + pat[i]) % MOD2;
    }

    // calculam hashuri partiale pentru text
    for (int i = 0; i < text.size(); ++i) {
        hash_text[i].x = (i64(hash_text[i - 1].x) * 128 + text[i]) % MOD1;
        hash_text[i].y = (i64(hash_text[i - 1].y) * 128 + text[i]) % MOD2;
    }

    // pow1 = 128^(pat.size()) % MOD1
    // pow2 = 128^(pat.size()) % MOD2
    pow1 = pow2 = 1;
    for (int i = 0; i < pat.size(); ++i) {
        pow1 = i64(pow1) * 128 % MOD1;
        pow2 = i64(pow2) * 128 % MOD2;
    }

    for (int i = 0; i + pat.size() - 1 < text.size(); ++i) {
        pii window_hash; // hash(text[i..i+pat.size() - 1])
        window_hash.x = (hash_text[i + pat.size() - 1].x - i64(hash_text[i - 1].x) * pow1) % MOD1;
        if (window_hash.x < 0)
            window_hash.x+= MOD1;
        window_hash.y = (hash_text[i + pat.size() - 1].y - i64(hash_text[i - 1].y) * pow2) % MOD2;
        if (window_hash.y < 0)
            window_hash.y+= MOD2;
        
        if (window_hash == hash_pat) {
            ans+= 1;
            if (occurences.size() < 1000)
                occurences.push_back(i);
        }
    }

    fo << ans << '\n';
    for (auto i: occurences)
        fo << i << ' ';
    fo << '\n';


    return 0;
}