Cod sursa(job #170232)

Utilizator DastasIonescu Vlad Dastas Data 2 aprilie 2008 16:06:34
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>

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

const int base = 3;

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

int n, m;
char a[maxn];
char c[maxc][maxl];
unsigned int h[maxc]; // h[i] = cuvantul i in baza base

int j = 1;

int p[maxl];

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

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

    return s;
}

void read()
{
    fgets(a, sizeof(a), in);

    n = strlen(a) - 1;

    fgets(c[1], 100, in);

    m = strlen(c[1]) - 1;

    for ( int i = 0; i < m; ++i )
        p[i] = pow(base, m - i - 1);
}

void getnr()
{
    unsigned int s = 0;

    for ( int i = 0; i < m; ++i )
    {
        c[j][i] = c[j][i] - 'a';

        s = s + p[i]*c[j][i];
    }

    h[j] = s;
}

int search(unsigned int what)
{
    int st = 1;
    int m = 0;
    int dr = j;

    while ( st < dr )
    {
        m = (st + dr) >> 1;

        if ( h[m] ==  what )
            return 1;
        else if ( h[m] > what )
            dr = m;
        else
            st = m + 1;
    }

    return 0;
}

int cnt;
int main()
{
    read();
    getnr();
    ++j;

    while ( fgets(c[j], 100, in) )
        getnr(), ++j;

    std::sort(h + 1, h + j + 1);

    unsigned int s = 0;

    for ( int i = 0; i < m; ++i )
        s = s + p[i]*(a[i] - 'a');

    if ( search(s) )
        ++cnt;

    for ( int i = m; i < n; ++i )
    {
        s = s - (p[0] * (a[i-m] - 'a'));
        s *= base;
        s = s + (a[i] - 'a');

        if ( search(s) )
            ++cnt;
    }

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

    return 0;
}