Cod sursa(job #1761478)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 22 septembrie 2016 12:30:42
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

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

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

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

inline void Insert(ll x){

    int n = x % MOD;
    for(int i = 0; i < Hash[n].size(); i++){

        if(Hash[n][i].first == x){

            Hash[n][i].second++;
            return;

        }
    }

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

}

inline int Find(ll x){

    int n = x % MOD;
    int ans = 0;
    for(int i = 0; i < Hash[n].size(); i++){

        if(Hash[n][i].first == x){

            ans = Hash[n][i].second;
            Hash[n][i].second = 0;
            return ans;

        }
    }

    return ans;

}

int main(){

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

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

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

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

    }

    x /= 3;
    Insert(x);

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

}