Cod sursa(job #2878634)

Utilizator Ana100Ana-Maria Tomoiala Ana100 Data 27 martie 2022 13:48:24
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
int base1=29,base2=31;
int mod1=66667,mod2=666013;
int HashA,HashB,HashC,HashD;
char str[10000001],a[21];
int power1,power2;
int lenghtA,lenghtstr;
int f1[66669],f2[666015];
int precalculate1()
{
    power1=1;
    for(int i=1;i<lenghtA;i++)
    {
        power1=(1LL*power1*base1)%mod1;
    }
    return power1;
}
int precalculate2()
{
    power2=1;
    for(int i=1;i<lenghtA;i++)
    {
        power2=(1LL*power2*base2)%mod2;
    }
    return power2;
}
int Create_HashA()
{
    HashA=0;
    for(int i=0;i<lenghtA;i++)
    {
        HashA=((1LL*HashA*base1)%mod1+a[i])%mod1;
    }
    return HashA;
}
int Create_HashC()
{
    HashC=0;
    for(int i=0;i<lenghtA;i++)
    {
        HashC=((1LL*HashC*base2)%mod2+a[i])%mod2;
    }
    return HashC;
}
int FindMatches()
{
    long long cnt=0;
    for(int i=0;i<lenghtA;i++)
    {
        HashB=((1LL*HashB*base1)%mod1+str[i])%mod1;
    }
    for(int i=0;i<lenghtA;i++)
    {
        HashD=((1LL*HashD*base2)%mod2+str[i])%mod2;
    }
    if(f1[HashB]!=0 and f2[HashD]!=0)
    {
        cnt++;
    }
    for(int i=lenghtA;i<lenghtstr;i++)
    {
        HashB=((HashB-str[i-lenghtA]*power1)%mod1+mod1)%mod1;
        HashB=((1LL*HashB*base1)%mod1+str[i])%mod1;
        HashD=((HashD-str[i-lenghtA]*power2)%mod2+mod2)%mod2;
        HashD=((1LL*HashD*base2)%mod2+str[i])%mod2;
        if(f1[HashB]!=0 and f2[HashD]!=0)
            cnt++;
    }
    return cnt;
}
int main()
{
    cin>>str;
    lenghtstr=strlen(str);
    cin>>a;
    lenghtA=strlen(a);
    precalculate1();
    precalculate2();
    int x=Create_HashA();
    f1[x]=1;
    int y=Create_HashC();
    f2[y]=1;
    while(cin>>a)
    {
        int x=Create_HashA();
        f1[x]=1;
        int y=Create_HashC();
        f2[y]=1;
    }
    cout<<FindMatches();
    return 0;
}