Cod sursa(job #3195147)

Utilizator DARIUSQSDarius Nicoara DARIUSQS Data 20 ianuarie 2024 10:31:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

char a[2000005], b[2000005];
long long p = 1007, mod = 1000000007;
vector < int > res;
int ans;
long long hash_a, hash_curent;
long long hash_b[2000005]; /// sume partiale pt hash-urile lui b
long long pw[2000005];
int n, m;
int main()
{
    f >> a >> b;
    n = strlen(a); m = strlen(b);
    /// creem puterile lui p
    pw[0] = 1;
    for (int i=1;i<m;i++) {
        pw[i] = (pw[i-1]*p) % mod;
    }
    /// calculam hash-ul sirului a
    for (int i=0;i<n;i++) {
        hash_a = (hash_a + a[i] * pw[i]) % mod;
    }
    /// calculam hash-urile sirului b
    hash_b[0] = b[0]; /// * pw[0];
    for (int i=1;i<m;i++) {
        hash_b[i] = (hash_b[i-1] + b[i] * pw[i]) % mod;
    }
    /// comparam hash-urile din b cu hash-ul lui a
    for (int i=0;i<=m-n;i++) {
        if (i==0) hash_curent = hash_b[i+n-1];
        else hash_curent = (hash_b[i+n-1] - hash_b[i-1] + mod)% mod;
        if ((hash_a * pw[i])%mod == hash_curent) {
            ans++;
            if (ans<=1000) {
                res.push_back(i);
            }
        }
    }
    g << ans << '\n';
    for (auto x:res) {
        g << x << " ";
    }
    return 0;
}