Cod sursa(job #837504)

Utilizator szabibibiOrban Szabolcs szabibibi Data 18 decembrie 2012 01:50:40
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <vector>
#include <string.h>

#define CMAX 10000002
#define NMAX 50000
#define LMAX 22
#define P 666013

using namespace std;

char cuv[CMAX];
vector <unsigned long> hash[P];
unsigned long harr;
long l, c;
long count;

unsigned long val(char *s)
{
    long i;
    unsigned long sol = 0;
    unsigned long t = 1;
    
    for (i = l - 1; i >= 0; i--)
    {
        sol += t * (s[i] - 'a');
        t = t * 3;
    }
    return sol;
}

void read()
{
     FILE *f = fopen("abc2.in", "r");
     char s[LMAX];
     unsigned long vall;
     
     fgets(cuv, CMAX, f);
     c = strlen(cuv) - 1;
     cuv[c] = '\0';

     fgets(s, LMAX, f);
     l = strlen(s) - 1;
     s[l] = '\0';

     vall = val(s);
     hash[vall % P].push_back(vall);

     while (fgets(s, LMAX, f) != NULL)
     {
           s[l] = '\0';
           vall = val(s);
           hash[vall % P].push_back(vall);
     }
     fclose(f);
}

unsigned long calc_put()
{
     int i;
     unsigned long p = 1;
     for (i = 1; i < l; i++)
         p = p * 3;
     return p;
}

int search_val(unsigned long vall)
{
    int i, n = hash[vall % P].size();
    for (i = 0; i < n; i++)
        if (hash[vall % P][i] == vall)
           return 1;
    return 0;
}

void dostuff()
{
     long i;
     unsigned long vall = val(cuv), sval, eval;
     if (search_val(vall))
        count++;
     harr = calc_put();
     for (i = 1; i <= c - l; i++)
     {
         sval = (cuv[i - 1] - 'a') * harr;
         eval = cuv[i + l - 1] - 'a';
         vall = (vall - sval) * 3 + eval;
         if (search_val(vall))
            count++;
     }
}

void print()
{
     FILE *f = fopen("abc2.out", "w");
     fprintf(f, "%ld", count);
     fclose(f);
}

int main()
{
    read();
    dostuff();
    print();
    return 0;
}