Cod sursa(job #2295966)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 4 decembrie 2018 01:49:28
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

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

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

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

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

    return s;
}

void getnr()
{
    int s = 0, i;

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

    h[j] = s;
}

int caut(int x)
{
    int st = 1, m = 0, dr = j;

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

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

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

    return 0;
}

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

    int ph, s = 0 ,i;

    fgets(a, maxn, in);

    n = strlen(a) - 1;

    fgets(c, 100, in);

    m = strlen(c) - 1;

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

    getnr();

    ++j;

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

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

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

    if ( caut(s) )
        ++cnt;

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

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

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

    fclose(in);
    fclose(out);

    return 0;
}