Cod sursa(job #98608)

Utilizator mariusdrgdragus marius mariusdrg Data 10 noiembrie 2007 15:05:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.56 kb
#include<stdio.h>


const int lemax = 10000100;

char a[lemax];
int i;
int prod;
int lung;

const int mod = 666013;
int an[mod + 2];
const int baz = 33;
#include<string>
int hash;
int ans;
char s[baz];


bool lit(char c)
{
        return c >= 'a' && c <= 'z';
}

int has(char *a)
{
        int ans = 0;
        for(i = 0;i <= lung; ++i)
        {
                ans *= baz;
                ans += a[i] - 'a';
                ans %= mod;
        }
        return ans;
        
}


int main()
{
        freopen("abc2.in","r",stdin);
        freopen("abc2.out","w",stdout);
        fgets(a,lemax,stdin);
        while(!feof(stdin))
        {
                fgets(s,30,stdin);
                lung = strlen(s) - 1;
                while(!lit(s[lung]))
                {
                        --lung;
                }
                an[has(s)] = 1;
        }
        ++lung;
        int prod = 1;
        for(i = 1;i <= lung; ++i)
        {
                prod *= baz;
                prod %= mod;
        }

        int n = strlen(a) - 1;
        while(!lit(a[n]))
        {
                --n;
        }

        for(i = 0;i <= n; ++i)
        {
                hash *= baz;
                hash %= mod;
                hash += a[i] - 'a';
                if (i >= lung)
                {
                        hash -= prod * (a[i - lung] - 'a');
                        while (hash < 0) hash += mod;
                }
                if (i >= lung - 1)
                {
                        ans += an[hash];
                }
        }
        printf("%d\n",ans);

        return 0;

}