Cod sursa(job #3304469)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 23 iulie 2025 23:13:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define NMAX 2000000
#define ll long long

using namespace std;

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

const int b = 127;
const int mod = 1000000007;

int n, m, cnt;
string pattern, text;
ll text_hash[NMAX + 2], pwr[NMAX + 2], pattern_hash = 0;
vector<int> poz;

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> pattern >> text;

    n = pattern.size();
    m = text.size();

    pwr[0] = 1;
    for (int i = 1; i <= NMAX; i++) {
        pwr[i] = (pwr[i - 1] * b) % mod;
    }

    for (int i = 0; i < n; i++) {
        pattern_hash = (pattern_hash * b + pattern[i]) % mod;
    }
    for (int i = 0; i < m; i++) {
        text_hash[i + 1] = (text_hash[i] * b + text[i]) % mod;
    }

    for (int i = n; i <= m; i++) {
        ll endhash = text_hash[i];
        ll starthash = text_hash[i - n];
        ll newhash = (starthash * pwr[n]) % mod;
        ll crrhash = (endhash - newhash + mod) % mod;

        if (crrhash == pattern_hash) {
            cnt++;
            if (cnt <= 1000) {
                poz.emplace_back(i - n);
            }
        }
    }

    fout << cnt << '\n';
    for (int pos : poz) {
        fout << pos << ' ';
    }
    return 0;
}