Cod sursa(job #3303082)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 13 iulie 2025 16:25:56
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int getHash(string &str) {
	int hsh = 0;
	for (int i = 0; i < str.size(); i++) {
		hsh = 3 * hsh + str[i] - 'a';
	}
	return hsh;
}

bool find(int val, vector <int> &v) {
	int ans = -1;
	for (int i = (1 << 15); i; i >>= 1) {
		if (ans + i < v.size() && v[ans + i] <= val) {
			ans += i;
		}
	}
	return ans != -1 && v[ans] == val;
}

void solve() {
	string str, s;
	cin >> str;
	vector <int> v;
	int n;
	while (cin >> s) {
		n = s.size();
		v.push_back(getHash(s));
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	int hsh = 0, p = 1, ans = 0;
	for (int i = 1; i < n; p *= 3, i++);

	for (int i = 0; i < str.size(); i++) {
		hsh = 3LL * hsh + str[i] - 'a';
		if (i + 1 >= n) {
			ans += find(hsh, v);
			hsh = hsh - (str[i - n + 1] - 'a') * p;
		}
	}
	cout << ans;
}

signed main() {
#ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    assert(freopen("test.out", "w", stdout));
#else
    assert(freopen("abc2.in", "r", stdin));
    assert(freopen("abc2.out", "w", stdout));
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nrt = 1;
    //cin >> nrt;
    while (nrt--) {
        solve();
    }
    return 0;
}