Cod sursa(job #2390302)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 27 martie 2019 21:44:02
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#define Kmax 25
#define Nmax 10000005
#define prime1 3
#define prime2 5
#define base1 666013
#define base2 100021

using namespace std;

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

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

char s[Nmax],word[Kmax];

int main(){

    f>>s;
    int lg;

    while(f>>word){

        int hash1=0,hash2=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;
        }

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

    int ans=0,i;

    int hash1=0,hash2=0;

    for(i=0;s[i] and i<lg;i++){

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

    if(i==lg){

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

    int diff1=1,diff2=1;

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

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

    for(;s[i];i++){

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

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

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

    g<<ans;

    return 0;
}