Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

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

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_back
typedef 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 ;p
int COUNTER, LAST_Q;
int trie[nax][26];
char sl[nax];
int where[nax]; // initially 0 for all N strings

void 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

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes