Cod sursa(job #1477198)

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

#define MOD 666013
#define MOD1 97
#define NMAX 50007
#define DIM 27
#define LIM 10000007

FILE *fin, *fout;
using namespace std;
int h, hh, sze1, sze2, ct, put[DIM], h2, hh2, put2[DIM];
char s[LIM], cuv[DIM], loc[MOD+7][MOD1+7];

void init()
{
    put[0] = 1;
    for(int i = 1; i< DIM; ++i)
    {
        put[i] = (put[i-1]*3)%MOD;
    }
    put2[0] = 1;
    for(int i = 1; i< DIM; ++i)
    {
        put2[i] = (put2[i-1]*3)%MOD1;
    }
}

void citire()
{
    scanf("%s", s+1);
    sze1= strlen(s+1);
    while(!feof(fin))
    {
        scanf("%s", cuv+1);
        if(!sze2) sze2 = strlen(cuv+1);
        h = 0;
        h2 = 0;
        for(int i = 1; i<= sze2; ++i)
        {
            h = (h + (cuv[i] - 'a')*put[sze2-i])%MOD;
            h2 = (h2 + (cuv[i] - 'a')*put2[sze2-i])%MOD1;
        }
        loc[h][h2] = 1;
    }
}

void solve()
{
    hh = 0;hh2 = 0;
    for(int i = 1; i<= sze2-1; ++i)
    {
        hh = (hh + (s[i] - 'a')*put[sze2-i])%MOD;
        hh2 = (hh2 + (s[i] - 'a')*put2[sze2-i])%MOD1;
    }
    for(int i = sze2; i<= sze1; ++i)
    {
        hh = (hh + (s[i] - 'a'))%MOD;
        hh2 = (hh2 + (s[i] - 'a'))%MOD1;
        if(loc[hh][hh2]) ct++;
        hh = ((hh - (s[i-sze2+1]-'a')*put[sze2-1] + MOD)*3)%MOD;
        hh2 = ((hh2 - (s[i-sze2+1]-'a')*put2[sze2-1] + MOD1)*3)%MOD1;
    }
}

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