Cod sursa(job #940396)

Utilizator rudarelLup Ionut rudarel Data 16 aprilie 2013 09:06:01
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MOD 666013
#define MAXP 25
#define MAXL 10000010
using namespace std;
char sir[MAXL], cuv[MAXP];
int pow[MAXP];
vector < unsigned int > hash[MOD];
 
inline int search(unsigned int x)
{
    unsigned int l = x % MOD;
    vector < unsigned int>::iterator it;
    for ( it = hash[l].begin(); it != hash[l].end(); it++)
    {
        if(*it == x)
            return 1;
    }
    return 0;
}
 
inline void add(unsigned int x)
{
    unsigned int l = x % MOD;
    hash[l].push_back(x);
}
 
int main()
{
    int N, M, i, b = 3, val, sol = 0;
    pow[0] = 1;
    for ( i = 1; i < MAXP; i++)
        pow[i] = pow[i-1] * b;
    FILE *fin = fopen("abc2.in", "r");
    fgets(sir, 10000002, fin);
    N = strlen(sir) - 2;
    fgets(cuv, 22, fin);
    M = strlen(cuv) - 2;
    while(!feof(fin))
    {
        if(strlen(cuv) - 2 == M)
        {
            val = 0;
            for ( i = 0; i <= M; i++)
                val = val * b + (cuv[i] - 'a');
            if(!search(val))
                add(val);
        }
        fgets(cuv, 22, fin);
    }
    fclose(fin);
    val = 0;
    for ( i = 0; i <= M; i++)
    {
        val = val * b + (sir[i] - 'a');
    }
    sol += search(val);
    for ( i = M+1; i <= N; i++)
    {
        val = (val - (sir[i-M-1] - 'a')*pow[M])*b + sir[i]-'a';
        sol += search(val);
    }
    FILE *fout = fopen("abc2.out","w");
    fprintf(fout, "%d\n", sol);
    fclose(fout);
    return 0;
}