Cod sursa(job #2729249)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 24 martie 2021 15:05:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;


string a,b;
// use unsigned for easy modulo
// hash[0] = (a[0]*p^n + a[1]*p^(n-1) + ... + a[n-1]*p + a[n])%mod
// hash[i] = hash[i-1]*p + a[n+i] - p^(n+1)*a[i-1];

void read(){
    ifstream in("strmatch.in");
    in >> a;
    in >> b;
    in.close();
}

void solve(){
    ofstream out("strmatch.out");
    const int p=31;
    const int mod=1e9 + 9;
    const int mod2=1e9 + 7;
    long long hash_a=0, hash_b=0, p_n=1;
    long long hash_a2=0, hash_b2=0, p_n2=1;
    vector<int> sol;
    for(unsigned int i=0; i<a.size(); i++){
        hash_a = (hash_a*p + a[i])%mod;
        hash_b = (hash_b*p + b[i])%mod;
        p_n=p_n*p%mod;
        hash_a2 = (hash_a2*p + a[i])%mod2;
        hash_b2 = (hash_b2*p + b[i])%mod2;
        p_n2=p_n2*p%mod2;
    }
    if(hash_a == hash_b && hash_b2 == hash_a2) sol.push_back(0);
    for(unsigned int i=a.size(); i<b.size() && sol.size()<1000; i++){
        hash_b = (mod + (hash_b*p - p_n*b[i-a.size()] + b[i])%mod)%mod;
        hash_b2 = (mod2 + (hash_b2*p - p_n2*b[i-a.size()] + b[i])%mod2)%mod2; 
        if(hash_b == hash_a && hash_a2 == hash_b2) sol.push_back(i-a.size()+1);
    }
    out << sol.size() << '\n';
    for(auto elem:sol){
        out << elem << ' ';
    }
    out.close();
}

int main(){
    read();
    solve();
}