Cod sursa(job #3036763)

Utilizator begusMihnea begus Data 24 martie 2023 22:59:29
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 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");

string t, s;
int P1, P2, slg, tlg, hashtable1[100007], hashtable2[100021];

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;
    while(fin >> s){
        slg=s.length();
        hashtable1[hash1(s)]=1;
        hashtable2[hash2(s)]=1;
    } 
    P1=P2=1;
    int hs1=hash1(t.substr(0, slg));
    int hs2=hash2(t.substr(0, slg));
    ans+=(hashtable1[hs1] && hashtable2[hs2]);
    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;
		ans+=(hashtable1[hs1] && hashtable2[hs2]);
    }
   fout << ans;
}