Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • 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
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Advance search problem solution

YASH PAL, 31 July 2024
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;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

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
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes