Cod sursa(job #3036755)

Utilizator begusMihnea begus Data 24 martie 2023 22:40:12
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

#define P 73
#define MOD1 100007
#define MOD2 100021

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

unordered_map<string, pair<int, int>> mp;
string t, s;
int P1, P2, slg, tlg;

int hash1(string s){
    int hs=0;
    for(int i=0; i<slg; i++){
        hs = P*hs+s[i];
        hs = hs%MOD1;
        if(i) P1=(P1*P)%MOD1;
    }
    return hs;
}

int hash2(string s){
    int hs=0;
    for(int i=0; i<slg; i++){
        hs = P*hs+s[i];
        hs = hs%MOD2;
        if(i) P2=(P2*P)%MOD2;
    }
    return hs;
}

int main(){
    fin >> t;
    tlg=t.length();
    int ans=0, i=1;
    while(fin >> s){
        slg=s.length();
        if(mp[s]==make_pair(0, 0)) mp[s]={hash1(s), hash2(s)};
    } 

    P1=P2=1;
    int hs1=hash1(t.substr(0, slg));
    int hs2=hash2(t.substr(0, slg));
    
    for(auto u : mp) if(u.second.first==hs1 && u.second.second==hs2) ans++;
    for(int i=slg; i<tlg; i++){
        hs1 = ((hs1 - (t[i - slg] * P1) % MOD1 + MOD1) * P + t[i]) % MOD1;
		hs2 = ((hs2 - (t[i - slg] * P2) % MOD2 + MOD2) * P + t[i]) % MOD2;
        for(auto u : mp) if(u.second.first==hs1 && u.second.second==hs2) ans++;
    }
   fout << ans;
}