Cod sursa(job #1764850)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 25 septembrie 2016 23:09:09
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

typedef unsigned int ui;

const int NMax = 5005;
const int MOD = 666013;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

vector < ui > Hash[MOD];
ui Power[30];

inline bool Find(const ui &x){

    vector < ui > ::iterator it;

    int key = x % MOD;
    for(it = Hash[key].begin(); it != Hash[key].end(); it++){

        if((*it) == x){
            return true;
        }

    }

    return false;

}

inline int Change(const char &c){
    return (c - 'a');
}

inline void Prepare(const string &s){

    ui val = 0;
    for(int i = 0; i < (int)s.size(); i++){
        val = val + Change(s[i]) * Power[i];
    }

    if(Find(val) == false){
        Hash[val % MOD].push_back(val);
    }

}

int main(){

    ios::sync_with_stdio(false);
    fin.tie(NULL);

    string s, a;
    fin >> s >> a;

    int n = (int)s.size();
    int m = (int)a.size();

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

    Prepare(a);
    while(fin >> a) Prepare(a);

    ui val = 0;
    for(int i = 0; i < m - 1; i++) val = val + Change(s[i]) * Power[i];

    int ans = 0;
    for(int i = m - 1; i < n; i++){

        val = val + Change(s[i]) * Power[m - 1];

        if(Find(val) == true) ans++;

        val /= 3;

    }

    fout << ans;

    return 0;

}