Cod sursa(job #106827)

Utilizator vlad_popaVlad Popa vlad_popa Data 18 noiembrie 2007 23:17:48
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.48 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <string>
#include <iostream>
#include <set>
#include <vector>

#define FIN "abc2.in"
#define FOUT "abc2.out"
#define NMAX 10000000

#define pb push_back

int N;
char s[NMAX], sir[21], l;
vector <int> H[100000];

void read ()
{
    long long sum = 0, trei;
    int i;
    
    gets (s);
    N = strlen (s);
    scanf ("\n");
    gets (sir);
    l = strlen (sir);
    for (i = 0, trei = 1; i < l; ++ i, trei *= 3)
        sum += trei * (sir[i] - 'a');
    H[(sum * 12313) % 99997].pb (sum);
    
    while (gets (sir))
    {
        sum = 0;
        for (i = 0, trei = 1; i < l; ++ i, trei *= 3)
            sum += trei * (sir[i] - 'a');
        H[(sum * 12313) % 99997].pb (sum);
    }
}

void solve ()
{
    int i, cnt = 0, sz, j;
    long long sum = 0, trei = 1;
    
    for (i = 0; i < l - 1; ++ i, trei *= 3)
        sum += trei * (s[i] - 'a');

    for (; i < N; ++ i)
    {
        sum += trei * (s[i] - 'a');
        sz = H[(sum*12313) % 99997].size();
        for (j = 0; j < sz; ++ j)
            if(H[(sum*12313) % 99997][j] == sum)
            {
                ++ cnt;
                break;
            }
        sum -= s[i - l + 1] - 'a';
        sum /= 3;
        //cout<< sum<<"\n";
    }
    
    printf ("%d\n", cnt);
}

int
 main ()
{
    freopen (FIN, "rt", stdin);
    freopen (FOUT, "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}