Cod sursa(job #3242818)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 14 septembrie 2024 11:01:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 2e6;
const int B = 127;
const int MOD = 1e9 + 7;
long long putere[NMAX + 1];
long long ht[NMAX + 1];

int main() {
    
    string p;
    string t;
    f >> p >> t;
    putere[0] = 1;
    for(int i = 1; i < max(p.size(), t.size()); i++) {
        putere[i] = (putere[i - 1] * B) % MOD;
    }
    //hash-ul pentru pattern
    long long hp = 0;
    for(int i = 0; i < p.size(); i++) {
        hp = (hp + (p[i] - '0' + 1) * putere[i]) % MOD;
    }
    //hash-ul pentru text
    ht[0] = (t[0] - '0' + 1);
    for(int i = 1; i < t.size(); i++) {
        ht[i] = (ht[i - 1] + (t[i] - '0' + 1) * putere[i]) % MOD;
    }
    int sz = p.size();
    vector<int> sol;
    for(int i = 0; i + sz - 1 < t.size(); i++) {
        long long h;
        if(i == 0) {
            h = ht[i + sz - 1];
        } else {
            h = (ht[i + sz - 1] - ht[i - 1] + MOD) % MOD;
        }
        if(h == (hp * putere[i]) % MOD) {
            sol.push_back(i);
            if(sol.size() >= 1000) {
                break;
            }
            //cout << i << ' ';
        }
    }
    g << sol.size() << '\n';
    for(int i = 0; i < sol.size(); i++) {
        g << sol[i] << ' ';
    }
    return 0;
}