Cod sursa(job #1695330)

Utilizator Vasile_RotaruVasea Rotaru Vasile_Rotaru Data 26 aprilie 2016 22:08:08
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<bits/stdc++.h>
#define Mod 66013

using namespace std;
char t[10000010],w[22];

vector<unsigned int> Hash[103000];
long long p[30],k=0;

void insert(unsigned int x){
    int pos=x%Mod,l,i;
    l=Hash[pos].size();
    for(i=0;i<l;i++)
        if(Hash[pos][i]==x)
            return;
    Hash[pos].push_back(x);
}

void find(unsigned int x){
    int pos=x%Mod,l,i;
    l=Hash[pos].size();
    for(i=0;i<l;i++)
        if(Hash[pos][i]==x){
            k++;
            return;
        }
}

int main(){
	
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    int l,len,i;
    unsigned int x;
    scanf("%s",&t);
    len=strlen(t);
    p[0]=1;
    for(i=1;i<=20;i++)p[i]=p[i-1]*3;
    while(scanf("%s",&w)!=EOF){
        x=0;
        l=strlen(w);
        for(i=0;i<l;i++)
            x=x*3+w[i]-'a';
        insert(x);
    }
    x=0;
    for(i=0;i<l;i++)
        x=x*3+t[i]-'a';
    find(x);
    for(i=l;i<len;i++){
        x=x-p[l-1]*(t[i-l]-'a');
        x=x*3+t[i]-'a';
        find(x);
    }
    printf("%lld",k);
    return 0;
}