Cod sursa(job #3319092)

Utilizator gabi072Sanda Gabriel gabi072 Data 30 octombrie 2025 15:10:12
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
unordered_map<int,int> mp;
const int base = 1315423911;
const int mod = 1e9+7;
int h[10000000],p;
string sir,c;
inline int hashd(const string &s) {
    int h=0;
    for (char i:s) {
        h=(1ll*h*base+i)%mod;
    }
    return h;
}
int main() {
    fin>>sir;
    fin>>c;
    int ws=c.size();
    h[0]=sir[0];
    p=1;
    for (int i=0;i<ws;++i)
        p=1ll*p*base%mod;
    for (int i=1;i<(int)sir.size();++i) {
        h[i]=(1ll*base*h[i-1]+sir[i])%mod;
    }
    for (int i=0;i<=(int)sir.size()-ws;++i) {
        int key;
        if (i==0)
            key=h[ws-1];
        else
            key=((h[i+ws-1]-1ll*h[i-1]*p)%mod+mod)%mod;
        mp[key]++;
    }
    long long ap=0;
    int key=hashd(c);
    ap+=mp[key];
    mp[key]=0;
    while (fin>>c) {
        int key=hashd(c);
        ap+=mp[key];
        mp[key]=0;
    }
    fout<<ap;
}