Cod sursa(job #1761981)

Utilizator DobosDobos Paul Dobos Data 23 septembrie 2016 10:23:18
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

const int MOD = 666013;
const int SMAX = 22;
const int NMAX = 10000005;
typedef unsigned int var;

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector < var > H[MOD];


char s[SMAX],S[NMAX];
var P[22];

int Hash(const var &x){
    int key = x % MOD;
    for(int i = 0; i < H[key].size(); i++){
        if(H[key][i] == x)
            return 1;
    }

    return 0;

}
int Tr(const char &x){
    return x - 'a';
}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    P[0] = 1;
    for(int  i = 1; i < 20 ; i++)
        P[i] = P[i - 1] * 3;

    fin >> S >> s;

    int n = strlen(S) , m = strlen(s) , r = 0;
    var a;

     do{
        a = 0;
        for(int i = 0; i < m; i++){
            a += Tr(s[i]) * P[i];
        }

        if(Hash(a) == 0){
          H[a % MOD].push_back(a);
        }



    }while(fin >> s);

    for(int i = 0; i < m; i ++)
        a += Tr(S[i]) * P[i];

    if(Hash(a) == 1)
        r++;

   for(int  i = m; i < n; i++){

        a /= 3;
        a += Tr(S[i]) * P[m - 1];
        if(Hash(a) == 1)
            r++;

    }

    fout << r;

    return 0;
}