Cod sursa(job #98312)

Utilizator mariusdrgdragus marius mariusdrg Data 10 noiembrie 2007 12:27:56
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.27 kb
#include<stdio.h>


const int lemax = 100000;
const int km = 10;


char a[lemax];
int i;
int prod[km];
int lung;
const int mod =  666013;
int an[km][mod + 2];
const int baz[9] = {0,3,33,13,17,23,71,73};
#include<string>
int hash[km];
int k;
int ans;
char s[40];


int min(int i,int j)
{
        return i > j ? j : i;
}

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

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


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;
                }
                has(s);
        }
        ++lung;
        int prod[10] = {1,1,1,1,1,1,1};
        for(k = 1;k <= 3; ++k)
        {
                for(i = 1;i <= lung; ++i)
                {
                        prod[k] *= baz[k];
                        prod[k] %= mod;
                }
        }

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

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

        return 0;

}