Cod sursa(job #1761468)

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

using namespace std;

typedef long long int ll;

const int NMax = 5005;

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

int main(){

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

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

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

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

    string aux;
    unordered_map < ll, int > uMap;
    ll x = 0;
    for(int i = 0; i < m; i++){

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

    }

    x /= 3;
    uMap[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');
        uMap[x]++;

    }

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

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

    }

    x /= 3;
    ans += uMap[x];
    uMap[x] = 0;

    while(fin >> a){

        x = 0;

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

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

        }

        x /= 3;
        ans += uMap[x];
        uMap[x] = 0;

    }

    fout << ans;

    return 0;

}