Cod sursa(job #1764849)

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

using namespace std;

typedef unsigned int ui;

const int NMax = 5005;
const int MOD = 100007;

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

vector < pair < ui, int > > Hash[MOD];

inline void Insert(ui x){

    int n = x % MOD;

    vector < pair < ui, int > > :: iterator it;
    for(it = Hash[n].begin(); it != Hash[n].end(); it++){

        if((*it).first == x){

            (*it).second++;
            return;

        }
    }

    Hash[n].push_back({x, 1});

}

inline int Find(ui x){

    int n = x % MOD;
    int ans = 0;

    vector < pair < ui, int > > :: iterator it;
    for(it = Hash[n].begin(); it != Hash[n].end(); it++){

        if((*it).first == x){

            ans = (*it).second;
            Hash[n].erase(it);
            return ans;

        }
    }

    return ans;

}

int main(){

    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    string s, a;
    cin >> s >> a;

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

    if(n < m){
        cout << 0;
        return 0;
    }

    ui x = 0;
    for(int i = 0; i < m; i++){

        x = (x + (s[i] - 'a')) * 3;

    }

    x /= 3;
    Insert(x);

    ui dif = 1;
    for(int i = 1; i < m; i++) dif *= 3;

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

        x = (x - (s[i - m] - 'a') * dif) * 3 + (s[i] - 'a');
        Insert(x);

    }

    int ans = 0;
    x = 0;
    for(int j = 0; j < m; j++){

        x = (x + (a[j] - 'a')) * 3;

    }

    x /= 3;
    ans += Find(x);

    while(cin >> a){

        x = 0;

        for(int j = 0; j < m; j++){

            x = (x + (a[j] - 'a')) * 3;

        }

        x /= 3;
        ans += Find(x);

    }

    cout << ans;

    return 0;

}