Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ```cpp
- #include <iostream>
- #include <cmath>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- typedef unsigned long long ull;
- const int PRIME_CONST = 29;
- const ull MAX_SIZE = INT_MAX;
- ull scratch_hash(string s) {
- ull hash = 0;
- for (short i = 0; i < s.length(); i++) {
- hash = (PRIME_CONST * hash + s[i]) % MAX_SIZE;
- }
- return hash;
- }
- int ground_truth(string latin, int len) {
- hash<string> hasher;
- unordered_set<size_t> mp;
- for (short i = 0; i < len - 1; i += 1) {
- string removed = latin.substr(0, i) + latin.substr(i + 2, len - 1);
- mp.insert(hasher(removed));
- }
- return mp.size();
- }
- void solve() {
- int len;
- string latin;
- cin >> len >> latin;
- unordered_set<ull> mp;
- ull prefix_hash = 0;
- ull postfix_hash = 0;
- ull old_bit_base = 1;
- for (int i = 0; i < len - 3; i += 1) {
- old_bit_base = (old_bit_base * PRIME_CONST) % MAX_SIZE;
- }
- for (short i = 2; i < len; i += 1) {
- postfix_hash = (postfix_hash * PRIME_CONST + latin[i]) % MAX_SIZE;
- }
- ull hash;
- for (short i = 0; i < len - 1; i += 1) {
- string prefix_string = latin.substr(0, i);
- string postfix_string = latin.substr(i + 2, len - 1);
- string removed = prefix_string + postfix_string;
- hash = (prefix_hash + postfix_hash) % MAX_SIZE;
- cout << "On string: " << removed << " hash " << hash << " expected " << scratch_hash(removed) << endl;
- cout << "Prefix : " << prefix_hash << " Postfix: " << postfix_hash << endl;
- mp.insert(hash);
- prefix_hash = (prefix_hash + latin[i] * old_bit_base) % MAX_SIZE;
- postfix_hash = (postfix_hash - latin[i+2] * old_bit_base) % MAX_SIZE;
- old_bit_base = (old_bit_base / PRIME_CONST) % MAX_SIZE;
- }
- cout << mp.size() << endl;
- }
- int main() {
- int n = 0;
- cin >> n;
- while (n--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement