Cod sursa(job #1761957)

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

const int MOD = 70853;
typedef long long var;

using namespace std;

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

string S,s;
var P[20];

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 = S.size(), m = s.size(), 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);
        }

        s.clear();

    }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;
}