In this HackerEarth Advanced search problem solution, You are given a string S of length N consisting of only lower case English alphabets. You will need to answer Q queries of the following types.
  1. 1 L R W: Find the number of occurrences of string W in substring [L,R] of string S.
  2. 1 L R U: Update the substring [L,R] of string S with string U.

HackerEarth Advance search problem solution


HackerEarth Advanced search problem solution.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 9;
bool grid[MAX_N][MAX_N];
int ans;

void bt() {
for (int i = 0; i < MAX_N; ++i)
for (int j = 0; j < MAX_N; ++j)
if (grid[i][j]) {
if (grid[i][j + 1]) {
grid[i][j] = grid[i][j + 1] = false;
bt();
grid[i][j] = grid[i][j + 1] = true;
}
if (grid[i + 1][j]) {
grid[i][j] = grid[i + 1][j] = false;
bt();
grid[i][j] = grid[i + 1][j] = true;
}
return;
}
++ans;
}

int main() {
ios::sync_with_stdio(0), cin.tie(0);
for (int i = 0; i < MAX_N - 1; ++i)
for (int j = 0; j < MAX_N - 1; ++j)
grid[i][j] = i >= 3 && i <= 4 || j >= 3 && j <= 4;
bt();
cout << ans << '\n';
}#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

#define ll long long

typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;

unordered_map <string, ordered_set> cache;
unordered_set<int> vis;
string s;

void updateSet(ordered_set &o, int sign, int pos) {
if (sign == -1) {
o.erase(pos);
} else {
o.insert(pos);
}
}

void cacheStrings(int l, int r, int n, int m, int sign) {
l = max(l, m - 1);
for (int i = l; i < n and i - m + 1 <= r; ++i) {
updateSet(cache[s.substr(i - m + 1, m)], sign, i);
}
}

void updateAndValidateCache(int l, int r, int n, string &w) {
for (auto z:vis) {
cacheStrings(l, r, n, z, -1);
}
for (int i = l; i <= r; ++i) {
s[i] = w[i - l];
}
for (auto z:vis) {
cacheStrings(l, r, n, z, 1);
}
}

int main() {

ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

int n, q;
cin >> n >> q >> s;
while (q-- > 00) {
int t, l, r;
string w;
cin >> t >> l >> r >> w;
l--, r--;
if (t == 1) {
if (!vis.count(w.size())) {
vis.insert(w.size());
cacheStrings(0, n - 1, n, w.size(), 1);
}
auto &z = cache[w];
int li = l + w.size() - 1;
cout << z.order_of_key(r + 1) - z.order_of_key(li) << "\n";
} else {
updateAndValidateCache(l, r, n, w);
}
}

return 0;
}