Cod sursa(job #2303254)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 15 decembrie 2018 22:00:24
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
char s[10000005],s2[25];
int len,len2;
#define MOD 9973
vector<pair<unsigned int,int> > H[MOD];
int query(unsigned int n){
    int h = n % MOD;
    for(auto &it : H[h])
        if(it.first == n){
            int aux = it.second;
            it = H[h].back();
            H[h].pop_back();
            return aux;
        }
    return 0;
}
void update(unsigned int n){
    int h = n % MOD;
    for(auto &it : H[h])
        if(it.first == n){
            ++it.second;
            return ;
        }
    H[h].push_back({n,1});
}
int main(){
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    scanf("%s",s);
    len=strlen(s);
    bool ok=0;
    int ans=0;
    unsigned int P=1;
    while(scanf("%s",s2)!=EOF){
        if(ok==0){
            len2=strlen(s2);
            unsigned int cod=0;
            for(int i=1;i<len2;++i)
                P*=3;
            for(int i=0;i<len2;++i)
                cod=cod*3+(s[i]-'a');
            for(int i=0;i<len-len2+1;++i){
                update(cod);
                cod=(cod-P*(s[i]-'a'))*3+(s[i+len2]-'a');
            }
        }
        unsigned int cod=0;
        for(int i=0;i<len2;++i)
            cod=cod*3+(s2[i]-'a');
        ans+=query(cod);
        ok=1;
    }
    printf("%d\n",ans);
	return 0;
}