Cod sursa(job #799570)

Utilizator cbanu96Banu Cristian cbanu96 Data 19 octombrie 2012 13:42:52
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MOD 50021
#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;
}