Cod sursa(job #170263)

Utilizator DastasIonescu Vlad Dastas Data 2 aprilie 2008 16:24:53
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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[maxl];
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, 100, in);

    m = strlen(c) - 1;

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

void getnr()
{
    int s = 0;

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

    h[j] = s;
}

int search(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;
    }

    if ( h[st] == what )
        return 1;

    return 0;
}

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

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

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

    int s = 0;

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

    if ( search(s) )
        ++cnt;

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

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

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

    return 0;
}