Cod sursa(job #2390311)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 27 martie 2019 21:55:47
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
#define Kmax 25
#define prime1 2
#define prime2 5
#define prime3 7
#define base1 666012
#define base2 100021
#define base3 4722

using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

bitset <base1> vis1;
bitset <base2> vis2;
bitset <base3> vis3;

char word[Kmax];
string s;

int main(){

    f>>s;
    int lg=0;

    while(f>>word){

        int hash1=0,hash2=0,hash3=0;
        lg=0;

        for(int i=0;word[i];i++){

            ++lg;
            hash1=(hash1*prime1+word[i]-'a')%base1;
            hash2=(hash2*prime2+word[i]-'a')%base2;
            hash3=(hash3*prime3+word[i]-'a')%base3;
        }

        vis1[hash1]=true;
        vis2[hash2]=true;
        vis3[hash3]=true;
    }

    int ans=0,i;

    int hash1=0,hash2=0,hash3=0;

    int N=s.size();
    if(N<lg){

        g<<0;
        return 0;
    }

    for(i=0;i<lg;i++){

        hash1=(hash1*prime1+s[i]-'a')%base1;
        hash2=(hash2*prime2+s[i]-'a')%base2;
        hash3=(hash3*prime3+s[i]-'a')%base3;
    }

    if(i==lg){

        if(vis1[hash1] and vis2[hash2] and vis3[hash3])
            ++ans;
    }

    int diff1=1,diff2=1,diff3=1;

    for(int j=1;j<lg;j++){

        diff1=(diff1*prime1)%base1;
        diff2=(diff2*prime2)%base2;
        diff3=(diff3*prime3)%base3;
    }

    for(;i<N;i++){

        hash1=(hash1-diff1*(s[i-lg]-'a')+base1)%base1;
        while(hash1<0)
            hash1+=base1;
        hash1=(hash1*prime1+s[i]-'a')%base1;

        hash2=(hash2-diff2*(s[i-lg]-'a')+base2)%base2;
        while(hash2<0)
            hash2+=base2;
        hash2=(hash2*prime2+s[i]-'a')%base2;

        hash3=(hash3-diff3*(s[i-lg]-'a')+base3)%base3;
        while(hash2<0)
            hash2+=base2;
        hash3=(hash3*prime3+s[i]-'a')%base3;

        if(vis1[hash1] and vis2[hash2] and vis3[hash3])
            ++ans;
    }

    g<<ans;

    return 0;
}