Cod sursa(job #492708)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 15 octombrie 2010 16:54:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#include <bitset>
#include <string>

using namespace std;

#define maxn 10000010
#define prim 2000009
#define baza 7

int n, i, j, k, sol, lg;
bitset<prim> f;
long long hs, pmax;
char s[maxn];
char c[25];

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    gets(s+1);
    while(gets(c+1))
    {
        lg=1;
        hs=0;
        while(c[lg]>0)
        {
            hs=(hs*baza+c[lg]-'a')%prim;
            ++lg;
        }
        f[hs]=1;
    }
    lg--;
    pmax=1;
    for(int i=1; i<=lg; ++i, pmax=(pmax*baza)%prim);
    hs=0;
    for(int i=1; s[i]!=0; ++i)
    {
        hs=(hs*baza+s[i]-'a')%prim;
        if(i>lg)
        {
            hs=(hs-1LL*pmax*(s[i-lg]-'a'));
            while(hs<0)
                hs+=prim;
            hs%=prim;
        }
        if(i>=lg && f[hs])
            sol++;
    }
    printf("%d\n", sol);
    return 0;
}