Cod sursa(job #106790)

Utilizator vlad_popaVlad Popa vlad_popa Data 18 noiembrie 2007 22:55:19
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.26 kb
using namespace std;

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

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

set <unsigned long> H;
int N;
char s[NMAX], sir[21], l;

void read ()
{
    unsigned 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.insert (sum);
    
    while (gets (sir))
    {
        sum = 0;
        for (i = 0, trei = 1; i < l; ++ i, trei *= 3)
            sum += trei * (sir[i] - 'a');
        H.insert (sum);
    }
}

void solve ()
{
    int i, cnt = 0;
    unsigned 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');
        if (H.find(sum) != H.end())
            ++ cnt;
        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;
}