Code : Non-Palindromic Substring
It’s possible to create a counter example for this hashing technique because we use a fixed ‘B’. If you want a more robust template, look at the next section.
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
class HashedString {
private:
// change M and B if you want
static const long long M = 1e9 + 9;
static const long long B = 9973;
// pow[i] contains B^i % M
static vector<long long> pow;
// p_hash[i] is the hash of the first i characters of the given string
vector<long long> p_hash;
public:
HashedString(const string &s) : p_hash(s.size() + 1) {
while (pow.size() < s.size()) {
pow.push_back((pow.back() * B) % M);
}
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
long long get_hash(int start, int end) {
long long raw_val =
(p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
return (raw_val % M + M) % M;
}
};
vector<long long> HashedString::pow = {1};
int calc_alternating_sum(vector<int> &pref, int l, int r) {
int up;
if (l % 2 == r % 2) {
up = r;
} else {
up = r - 1;
}
return pref[up] - (l - 2 >= 0 ? pref[l - 2] : 0);
}
void solve() {
int n, q;
cin >> n >> q;
string str;
cin >> str;
string rev = str;
reverse(rev.begin(), rev.end());
HashedString hash(str), revhash(rev);
vector<vector<int>> dp(26, vector<int>(n, 0));
// dp[ch][i] is 1 if str[i] == ch.
for (int i = 0; i < n; i++) {
dp[str[i] - 'a'][i] = 1;
}
auto pref = dp;
for (int ch = 0; ch < 26; ch++) {
auto &vec = pref[ch];
for (int i = 0; i < n; i++) {
if (i - 2 >= 0) {
vec[i] += vec[i - 2];
}
}
}
for (int zz = 0; zz < q; zz++) {
int l, r;
cin >> l >> r;
l--, r--;
int odd = str[l] - 'a';
int even = str[l + 1] - 'a';
int odd_freq = calc_alternating_sum(pref[odd], l, r);
int even_freq = calc_alternating_sum(pref[even], l + 1, r);
// Answer can overflow!!!
long long len = r - l + 1;
long long ans;
if (odd_freq + even_freq == len) {
if (odd == even) {
// All elements are equal
ans = 0;
} else {
// Alternating sequence
len /= 2;
ans = 2 * len * (len + 1) / 2;
}
} else {
ans = len * (len - 1) / 2 - 1;
if (hash.get_hash(l, r) != revhash.get_hash(n - 1 - r, n - 1 - l)) {
ans += len;
}
}
cout << ans << endl;
}
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
solve();
}
return 0;
}
This code is same as the previous ones, except here B is picked randomly during runtime. This makes it extremely difficult for anyone to create special counter example for hash collisions.
If you are a beginner and none of this makes sense to you, the summary is : you should use the hashing template from the 2nd section of USACO guide instead of the first section. Think of it as being similar to why you use map instad of unordered_map to prevent TLEs.
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
class HashedString {
private:
// change M and B if you want
static const long long M = 1e9 + 9;
static const long long B;
// pow[i] contains B^i % M
static vector<long long> pow;
// p_hash[i] is the hash of the first i characters of the given string
vector<long long> p_hash;
public:
HashedString(const string &s) : p_hash(s.size() + 1) {
while (pow.size() < s.size()) {
pow.push_back((pow.back() * B) % M);
}
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
long long get_hash(int start, int end) {
long long raw_val =
(p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
return (raw_val % M + M) % M;
}
};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
vector<long long> HashedString::pow = {1};
const long long HashedString::B =
uniform_int_distribution<long long>(0, M - 1)(rng);
int calc_alternating_sum(vector<int> &pref, int l, int r) {
int up;
if (l % 2 == r % 2) {
up = r;
} else {
up = r - 1;
}
return pref[up] - (l - 2 >= 0 ? pref[l - 2] : 0);
}
void solve() {
int n, q;
cin >> n >> q;
string str;
cin >> str;
string rev = str;
reverse(rev.begin(), rev.end());
HashedString hash(str), revhash(rev);
vector<vector<int>> dp(26, vector<int>(n, 0));
// dp[ch][i] is 1 if str[i] == ch.
for (int i = 0; i < n; i++) {
dp[str[i] - 'a'][i] = 1;
}
auto pref = dp;
for (int ch = 0; ch < 26; ch++) {
auto &vec = pref[ch];
for (int i = 0; i < n; i++) {
if (i - 2 >= 0) {
vec[i] += vec[i - 2];
}
}
}
for (int zz = 0; zz < q; zz++) {
int l, r;
cin >> l >> r;
l--, r--;
int odd = str[l] - 'a';
int even = str[l + 1] - 'a';
int odd_freq = calc_alternating_sum(pref[odd], l, r);
int even_freq = calc_alternating_sum(pref[even], l + 1, r);
// Answer can overflow!!!
long long len = r - l + 1;
long long ans;
if (odd_freq + even_freq == len) {
if (odd == even) {
// All elements are equal
ans = 0;
} else {
// Alternating sequence
len /= 2;
ans = 2 * len * (len + 1) / 2;
}
} else {
ans = len * (len - 1) / 2 - 1;
if (hash.get_hash(l, r) != revhash.get_hash(n - 1 - r, n - 1 - l)) {
ans += len;
}
}
cout << ans << endl;
}
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
solve();
}
return 0;
}