Cod sursa(job #3036758)

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

#define P 73
#define MOD1 100007

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

string t, s;
int P1, slg, tlg, hashtable[100007];

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 main(){
    fin >> t;
    tlg=t.length();
    int ans=0, i=1;
    while(fin >> s){
        slg=s.length();
        hashtable[hash1(s)]=1;;
    } 
    P1=1;
    int hs1=hash1(t.substr(0, slg));
    ans+=hashtable[hs1];
    for(int i=slg; i<tlg; i++){
        hs1 = ((hs1 - (t[i - slg] * P1) % MOD1 + MOD1) * P + t[i]) % MOD1;
		ans+=hashtable[hs1];
    }
   fout << ans;
}