Cod sursa(job #2303225)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 15 decembrie 2018 21:13:29
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
char s[10000005],s2[25];
int len,len2;
#define MOD 9973
struct HashInt{
    vector<unsigned int> H[MOD];
    bool find(unsigned int n){
        int h = n % MOD;
        for(auto it : H[h])
            if(it == n)
                return 1;
        return 0;
    }
    void insert(unsigned int n){
        int h = n % MOD;
        for(auto it : H[h])
            if(it == n)
                return ;
        H[h].push_back(n);
    }
};
HashInt Ap;
int main(){
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    cin>>s;
    len=strlen(s);
    int ans=0;
    unsigned int P=1;
    while(cin>>s2){
        len2=strlen(s2);
        unsigned int cod=0;
        for(int i=0;i<len2;++i)
            cod=cod*3+(s2[i]-'a');
        Ap.insert(cod);
    }
    for(int i=1;i<len2;++i)
        P*=3;
    unsigned int cod=0;
    for(int i=0;i<len2;++i)
        cod=cod*3+(s[i]-'a');
    for(int i=0;i<len-len2+1;++i){
            ans+=Ap.find(cod);
            cod=(cod-P*(s[i]-'a'))*3+(s[i+len2]-'a');
    }
    cout<<ans<<"\n";
	return 0;
}