Cod sursa(job #1520668)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 9 noiembrie 2015 10:22:59
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<cstdio>
#include<vector>
#include<cstring>
#define mod 102931
using namespace std;
char text[10000010],word[22];
vector<unsigned int> table[103000];
long long pow[30],answer=0;
void insert_in_table(unsigned int h){
    int poz=h%mod,dim,i;
    dim=table[poz].size();
    for(i=0;i<dim;i++)
        if(table[poz][i]==h)
            return;
    table[poz].push_back(h);
}
void get_count(unsigned int h){
    int poz=h%mod,dim,i;
    dim=table[poz].size();
    for(i=0;i<dim;i++)
        if(table[poz][i]==h){
            answer++;
            return;
        }
}
int main(){
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    int l,length,i;
    unsigned int h;
    scanf("%s",&text);
    length=strlen(text);
    pow[0]=1;
    for(i=1;i<=20;i++)
        pow[i]=pow[i-1]*3;
    while(scanf("%s",&word)!=EOF){
        h=0;
        l=strlen(word);
        for(i=0;i<l;i++)
            h=h*3+word[i]-'a';
        insert_in_table(h);
    }
    h=0;
    for(i=0;i<l;i++)
        h=h*3+text[i]-'a';
    get_count(h);
    for(i=l;i<length;i++){
        h=h-pow[l-1]*(text[i-l]-'a');
        h=h*3+text[i]-'a';
        get_count(h);
    }
    printf("%lld",answer);
    return 0;
}