Cod sursa(job #1477236)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 25 august 2015 19:25:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <cstring>

#define MOD1 1013
#define MOD2 97
#define MOD3 53
#define DIM 27
#define DIM_TXT 10000007

using namespace std;
int h1, h2, h3, put1[DIM], put2[DIM], put3[DIM], ct, n, sze;
char s[DIM], txt[DIM_TXT], loc[MOD1+2][MOD2+2][MOD3+2];

void init()
{
    put1[0] = 1;
    for(int i = 1; i< DIM; ++i) put1[i] = (3*put1[i-1])%MOD1;
    put2[0] = 1;
    for(int i = 1; i< DIM; ++i) put2[i] = (3*put2[i-1])%MOD2;
    put3[0] = 1;
    for(int i = 1; i< DIM; ++i) put3[i] = (3*put3[i-1])%MOD3;
}
void citire()
{
    scanf("%s", txt+1);
    n = strlen(txt+1);
    while(scanf("%s", s+1) == 1)
    {
        if(!sze) sze = strlen(s+1);
        h1 = 0;
        h2 = 0;
        h3 = 0;
        for(int i = 1; i<= sze; ++i)
        {
            h1 = (h1 + put1[sze-i] * (s[i] - 'a'))%MOD1;
            h2 = (h2 + put2[sze-i] * (s[i] - 'a'))%MOD2;
            h3 = (h3 + put3[sze-i] * (s[i] - 'a'))%MOD3;
        }
        loc[h1][h2][h3] = 1;
        //printf("%s\n", s+1);
        //printf("h1 = %d h2 = %d h3 = %d\n", h1, h2, h3);
    }
}
void solve()
{
    h1 = 0;
    h2 = 0;
    h3 = 0;
    for(int i = 1; i< sze; ++i)
    {
        h1 = (h1 + (txt[i]-'a')*put1[sze-i])%MOD1;
        h2 = (h2 + (txt[i]-'a')*put2[sze-i])%MOD2;
        h3 = (h3 + (txt[i]-'a')*put3[sze-i])%MOD3;
    }
    for(int i = sze; i<= n; ++i)
    {
        h1 = h1 + txt[i] - 'a'; if(h1 >= MOD1) h1 -= MOD1;
        h2 = h2 + txt[i] - 'a'; if(h2 >= MOD2) h2 -= MOD2;
        h3 = h3 + txt[i] - 'a'; if(h3 >= MOD3) h3 -= MOD3;
        //printf("%s\n", txt +i-sze+1);
        //printf("h1 = %d h2 = %d h3 = %d\n", h1, h2, h3);
        if(loc[h1][h2][h3] == 1) ct++;
        h1 = ((h1 - (txt[i-sze+1]-'a')*put1[sze-1] + MOD1)*3)%MOD1;
        h2 = ((h2 - (txt[i-sze+1]-'a')*put2[sze-1] + MOD2)*3)%MOD2;
        h3 = ((h3 - (txt[i-sze+1]-'a')*put3[sze-1] + MOD3)*3)%MOD3;
    }
}

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    init();
    citire();
    solve();
    printf("%d\n", ct);
    return 0;
}