Cod sursa(job #1761337)

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

const int NMAX = 1e8;
const int MOD = 70853;

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector < int > H[MOD];
string S,s;
bitset < NMAX > F;

int Hash(const int &x){
    int r = 0;
    for(int i = 0; i < H[x % NMAX].size(); i++){
        if(H[x % NMAX][i] == x)
            r++;
    }

    return r;

}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);
    fin >> S >> s;
    int n = S.size(), m = s.size(),a, r = 0;

    for(int  i = 0; i <= n - m; i++){
        a = 0;
        for(int j = 0,k = i; j < m; j++,k++){
            a += S[k] * pow(3,j);
        }
        H[a % MOD].push_back(a);
    }
    do{
        a = 0;
        for(int i = 0; i < m; i++){
            a += s[i] * pow(3,i);
        }
        if(F[a] == 0){
          r += Hash(a);
          F[a] = 1;
        }
        s.clear();

    }while(fin >> s);

    fout << r;

    return 0;
}