Cod sursa(job #2871583)

Utilizator Danut200333Dumitru Daniel Danut200333 Data 15 martie 2022 09:49:32
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
#define MOD1 12289
//#define MOD2 1000000013
#define hash1 3
//#define hash2 37
string A,B;
map <long long,bool> h;
unsigned long long sol,p1,p2,hashB1,hashA1,hashB2,hashA2,n,m,i;
int main()
{
    fin>>A;
    while(fin>>B)
    {
        m=B.size();
        hashB1=0;
        //fout<<B[0]-'a'<<'\n';
        for(i=0; i<m; ++i)
        {
            hashB1=((hashB1*hash1)%MOD1+(B[i]-'a'))%MOD1;
            //hashB2=((hashB2*hash2)%MOD2+B[i])%MOD2;
        }
        h[hashB1]=1;
    }
    p1=1;
    n=A.size();
    for(i=0; i<m; ++i)
    {
        hashA1=((hashA1*hash1)%MOD1+(A[i]-'a'))%MOD1;
        //hashA2=((hashA2*hash2)%MOD2+A[i])%MOD2;
        if(i>0)
        {
            p1=(p1*hash1)%MOD1;
            //p2=(p2*hash2)%MOD2;
        }
    }
    if(h[hashA1]==1)sol++;
    for(i=m; i<n; ++i)
    {
        hashA1=((hash1*(hashA1-(((A[i-m]-'a')*p1)%MOD1)+MOD1))%MOD1+(A[i]-'a'))%MOD1;
        //hashA2=((hash2*(hashA2-((A[i-m]*p2)%MOD2)+MOD2))%MOD2+A[i])%MOD2;
        if(h[hashA1]==1)sol++;
    }
    fout<<sol;
    return 0;
}