Cod sursa(job #98543)

Utilizator DastasIonescu Vlad Dastas Data 10 noiembrie 2007 14:20:06
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.11 kb
#include <cstdio>
#include <cstring>

const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;

const int maxp = 666013;

FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");

char a[maxn];
int p[maxn];

int n, m;
char c[maxl];

int h[maxp];

int pow(int a, int b)
{
    int s = 1;

    for ( int i = 1; i <= b; ++i )
        s *= a;

    return s;
}

int getnr()
{
    int r = 0;

    int k = n - 1;
    for ( int i = 0; i < n; ++i )
        r = (r + (c[i]-'a')*pow(3,k--)) % maxp;

    return r;
}

int check(int x, int y)
{
    int r = 0;

    int k = n - 1;
    for ( int i = x; i < y; ++i )
        r = (r + (a[i]-'a')*pow(3,k--)) % maxp;

    return r;
}

int cnt;
int main()
{
    fscanf(in, "%s", a);
    m = strlen(a);

    fscanf(in, "%s", c);
    n = strlen(c);

    ++h[ getnr() ];
   // printf("%d\n", getnr());

    while ( fscanf(in, "%s", c) == 1 )
        ++h[ getnr() ];//, printf("%d\n", getnr());;

    //printf("\n\n");
    for ( int i = 0; i < m; ++i )
    {
        int k = i + n;
        if ( k >= m )
            break;

        //printf("%d\n", check(i, k));
        if ( h[ check(i, k) ] )
            ++cnt;
    }

    fprintf(out, "%d\n", cnt);

    return 0;
}

//int getpref()
//{
//    p[1] = 0;
//
//    int k = 0;
//    int i;
//    for ( i = 2; c[i]; ++i )
//    {
//        while ( k > 0 && c[k+1] != c[i] )
//            k = p[k];
//
//        if ( c[k+1] == c[i] )
//            ++k;
//
//        p[i] = k;
//    }
//
//    n = i-1;
//}
//
//char viz[maxn];
//int main()
//{
//    fscanf(in, "%s", a+1);
//
//    int cnt = 0;
//    while ( fscanf(in, "%s", c+1) == 1 )
//    {
//        int q = 0;
//        getpref();
//
//        for ( int i = 1; a[i]; ++i )
//        {
//            while ( q > 0 && c[q+1] != a[i] )
//                q = p[q];
//            if ( c[q+1] == a[i] )
//                ++q;
//
//            if ( q == n && !viz[i-n+1] )
//                ++cnt, viz[i-n+1] = 1;
//        }
//    }
//
//    fprintf(out, "%d\n", cnt);
//
//	return 0;
//}