HackerEarth Yet another problem with Strings solution YASH PAL, 31 July 2024 In this HackerEarth Yet another problem with Strings problem solution You are given a 0-indexed array S with N strings, numbered 0 through N-1, and Q queries to handle. All strings in this problem are nonempty and consist of lowercase English letters.Let’s create an integer variable LAST_YES to decipher the input. LAST_YES should be equal to the index of the last query that was of the first type and had an answer “YES”. Queries are 0-indexed. LAST_YES is initially equal to zero. Note that LAST_YES can’t be changed in the first query because the first query’s index is zero.There are two types of queries.The first type is of ciphered form “1 t”, where t is a string of lowercase English characters. Add LAST_YES to each character in t to get its deciphered value. E.g. the given string cdxyyz with LAST_YES equal to 2 denotes a deciphered string efzaab. You should check whether at least one element of S is a substring of deciphered t. In a single line print “YES” or “NO”.The second type is of ciphered form “2 i alpha”, where i and alpha are integers.i (0 ≤ i < |S|) denotes an index in the array S.alpha (0 ≤ alpha < 26) denotes a single lowercase English letter.To decipher a query you should add LAST_YES to i and to alpha. In the other words, you can get a deciphered values using the following C++ and Java code:i = (i + LAST_YES) % N;alpha = (alpha + LAST_YES) % 26;After deciphering a query you should add a letter alpha at the end of the i-th string in S.HackerEarth Yet another problem with Strings problem solution.#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 100, pr = 53, pr2 = 59, pr3 = 14243, bpr = 1e9 + 21, SZ = 1 << 20;int nxt[N][26];int add[N], now[N], len[N];int sz;bool no_p[N];int pos[N];int p[N], p2[N];vector <pair <pair <int, int>, int> > Map[SZ];int h[N], h2[N], h_tree[N], h_tree2[N];inline void Insert (const pair <int, int> &h, const int &x) { int pos = (h.first + h.second * 1ll * pr3) % SZ; for (auto it : Map[pos]) if (it.first == h) return; Map[pos].emplace_back (make_pair (h, x));}inline void Delete (const pair <int, int> &h) { int pos = (h.first + h.second * 1ll * pr3) % SZ; for (int it = 0; it < Map[pos].size (); ++it) { if (Map[pos][it].first == h) { Map[pos].erase (Map[pos].begin () + it); return; } } }inline int Find (const pair <int, int> &h) { int pos = (h.first + h.second * 1ll * pr3) % SZ; for (auto it : Map[pos]) if (it.first == h) return it.second; return -1;}inline int add_s (const string &s) { int v = 0; for (auto ch : s) { if (!nxt[v][ch - 'a']) nxt[v][ch - 'a'] = ++sz; v = nxt[v][ch - 'a']; } ++add[v]; return v;}inline int get_hash (const int &h, const int &pw) { return (h * 1ll * p[N - 1 - pw]) % bpr;}inline int get_hash2 (const int &h, const int &pw) { return (h * 1ll * p2[N - 1 - pw]) % bpr;}inline void dfs_1 (const int &v, int pref_sum) { pref_sum += add[v]; now[v] = pref_sum; add[v] = 0; Insert (make_pair (get_hash (h_tree[v], 0), get_hash2 (h_tree2[v], 0)), v); for (int ch = 0; ch < 26; ++ch) { int to = nxt[v][ch]; if (!to) continue; len[to] = len[v] + 1; h_tree[to] = (h_tree[v] + ((ch + 1) * 1ll * p[len[v]])) % bpr; h_tree2[to] = (h_tree2[v] + ((ch + 1) * 1ll * p2[len[v]])) % bpr; dfs_1 (to, pref_sum); }}inline void dfs_2 (const int &v) { if (no_p[v]) return; int x = add[v] + now[v]; assert (x >= 0); if (x > 0) return; no_p[v] = 1; for (int ch = 0; ch < 26; ++ch) { int to = nxt[v][ch]; if (!to) continue; add[to] += add[v]; dfs_2 (to); } add[v] = 0;}int main () { #ifdef LOCAL freopen ("in", "r", stdin); freopen ("out", "w", stdout); #endif ios_base :: sync_with_stdio (0); cin.tie (0); p[0] = 1; p2[0] = 1; for (int i = 1; i < N; ++i) { p[i] = (p[i - 1] * 1ll * pr) % bpr; p2[i] = (p2[i - 1] * 1ll * pr2) % bpr; } int n, q; cin >> n >> q; for (int i = 0; i < n; ++i) { string s; cin >> s; pos[i] = add_s (s); } dfs_1 (0, 0); dfs_2 (0); int lastq = 0; string t; for (int test = 0; test < q; ++test) { int q_type; cin >> q_type; if (q_type == 1) { cin >> t; h[0] = (t[0] - 'a' + 1); h2[0] = (t[0] - 'a' + 1); bool ans = 0; for (int i = 1; i < t.size (); ++i) { h[i] = (h[i - 1] + ((t[i] - 'a' + 1) * 1ll * p[i])) % bpr; h2[i] = (h2[i - 1] + ((t[i] - 'a' + 1) * 1ll * p2[i])) % bpr; } for (int i = t.size () - 1; i >= 0; --i) { int l = i, r = t.size (); while (r - l > 1) { int mid = (r + l) >> 1; auto g = make_pair ((h[mid] - h[i] + bpr) % bpr, (h2[mid] - h2[i] + bpr) % bpr); g.first = get_hash (g.first, i + 1); g.second = get_hash2 (g.second, i + 1); if (Find (g) == -1) r = mid; else l = mid; } auto g = make_pair ((h[l] - h[i] + bpr) % bpr, (h2[l] - h2[i] + bpr) % bpr); g.first = get_hash (g.first, i + 1); g.second = get_hash2 (g.second, i + 1); int v = Find (g); ans |= (!no_p[v]); } int l = -1, r = t.size (); while (r - l > 1) { int mid = (r + l) >> 1; auto g = make_pair (h[mid], h2[mid]); g.first = get_hash (g.first, 0); g.second = get_hash2 (g.second, 0); if (Find (g) == -1) r = mid; else l = mid; } if (l > -1) { auto g = make_pair (h[l], h2[l]); g.first = get_hash (g.first, 0); g.second = get_hash2 (g.second, 0); int v = Find (g); ans |= (!no_p[v]); } cout << (ans ? "YESn" : "NOn"); if (ans) lastq = test; } else { int j, alpha; cin >> j >> alpha; j = (j + lastq) % n; alpha = (alpha + lastq) % 26; int v = pos[j]; if (!nxt[v][alpha]) { nxt[v][alpha] = ++sz; now[sz] = now[v]; len[sz] = len[v] + 1; h_tree[sz] = (h_tree[v] + ((alpha + 1) * 1ll * p[len[v]])) % bpr; h_tree2[sz] = (h_tree2[v] + ((alpha + 1) * 1ll * p2[len[v]])) % bpr; Insert (make_pair (get_hash (h_tree[sz], 0), get_hash2 (h_tree2[sz], 0)), sz); } --add[v]; ++add[nxt[v][alpha]]; dfs_2 (v); pos[j] = nxt[v][alpha]; } } return 0;}Second solution#include<bits/stdc++.h>using namespace std;#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)#define FORD(i,a,b) for(int i = (a); i >= (b); --i)#define RI(i,n) FOR(i,1,(n))#define REP(i,n) FOR(i,0,(n)-1)#define mp make_pair#define pb push_backtypedef long long ll;const int inf = 1e9 + 5;const int nax = 1e6 + 15;vector<pair<int,int> > H = vector<pair<int,int> > { make_pair(27, 1000*1000*1000 + 7), //make_pair(61, 1000*1000*1000 + 9), make_pair(101,1000*1000*1001 + 27)};const int K = H.size();const vector<int> HASH_ZERO = vector<int>(K, 0);vector<int> powers[nax];void initPowers() { powers[0] = vector<int>{1, 1, 1}; RI(i, nax-1) { REP(j, K) { ll tmp = (ll) powers[i-1][j] * H[j].first; powers[i].pb(int(tmp % H[j].second)); } }}vector<int> mul(vector<int> w, int len) { REP(i, K) w[i] = (ll) w[i] * powers[nax-1-len][i] % H[i].second; return w;}vector<int> sub(vector<int> a, vector<int> b) { REP(i, K) a[i] = (a[i] - b[i] + H[i].second) % H[i].second; return a;}vector<int> extendHash(vector<int> w, int ch) { for(int i = 0; i < K; ++i) { ll tmp = (ll) w[i] * H[i].first + ch + 1; w[i] = tmp % H[i].second; } return w;}struct Node { int endHere = 0; int sum = 0; // sum over endHere of ansectors, including me vector<int> hash;} node[nax];map<vector<int>, int> mapHash; // not hashmap ;pint COUNTER, LAST_Q;int trie[nax][26];char sl[nax];int where[nax]; // initially 0 for all N stringsvoid update(int a) { REP(i, 26) { int b = trie[a][i]; if(b == 0) continue; bool before = (bool) node[b].sum; node[b].sum = node[a].sum + node[b].endHere; if(before != (bool) node[b].sum) update(b); }}int len[nax];void addLetter(int id, int ch) { ++len[id]; int v = where[id]; int & child = trie[v][ch]; if(!child) { child = ++COUNTER; node[child].hash = extendHash(node[v].hash, ch); mapHash[mul(node[child].hash, len[id])] = child; } where[id] = child; node[v].endHere--; node[v].sum--; node[child].endHere++; update(v);}void queryAdd(int n) { int i, j; scanf("%d%d", &i, &j); assert(0 <= i && 0 <= j && i < n && j < 26); addLetter((i + LAST_Q) % n, (j + LAST_Q) % 26);}vector<int> t[nax];bool queryCheck() { static ll total = 0; scanf("%s", sl); int d = strlen(sl); total += d; assert(total <= 500 * 1000); for(int i = 0; i < d; ++i) assert('a' <= sl[i] && sl[i] <= 'z'); for (int i = 0; i < d; ++i) sl[i] = 'a' + ((sl[i] - 'a' + LAST_Q) % 26); t[0] = HASH_ZERO; FOR(i,1,d) t[i] = extendHash(t[i-1], sl[i-1] - 'a'); REP(i, d) { int low = i - 1, high = d - 1; while(low < high) { int j = (low + high + 1) / 2; vector<int> interval = sub(mul(t[j+1], j+1), mul(t[i], i)); interval = mul(interval, nax-1 - i); auto it = mapHash.find(interval); if(it == mapHash.end()) high = j -1; else { low = j; if(node[(*it).second].endHere) return true; } } } return false;}int main() { initPowers(); int n, q; scanf("%d%d", &n, &q); assert(1 <= min(n, q) && max(n, q) <= 500 * 1000); node[0].endHere = node[0].sum = n; node[0].hash = HASH_ZERO; ll total = 0; REP(id, n) { scanf("%s", sl); int d = strlen(sl); total += d; REP(j, d) assert('a' <= sl[j] && sl[j] <= 'z'); REP(j, d) addLetter(id, sl[j] - 'a'); } assert(total <= 500 * 1000); REP(i, q) { int which; scanf("%d", &which); assert(1 <= which && which <= 2); if(which == 1) { bool ans = queryCheck(); puts(ans ? "YES" : "NO"); if(ans) LAST_Q = i; } else queryAdd(n); } return 0;} coding problems solutions