HackerEarth One mismatch problem solution YASH PAL, 31 July 2024 In this HackerEarth One mismatch problem solution we have given a string s and a set of n strings pi. For each i find the number of occurrences of pi in s with at most one k-length gap. The string s occurs in string t at position p with at most one k-length gap if strings s and tptp+1 … tp+|s|-1 are equal with at most one k-length gap. Strings s and r are equal with at most one k-length gap if: |s| = |r|; or all i and j such that si != ri and sj != rj, it holds |i – j| < k. HackerEarth One mismatch problem solution. #include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <cmath>#include <ctime>#include <functional>#include <sstream>#include <fstream>#include <valarray>#include <complex>#include <queue>#include <cassert>#include <bitset>using namespace std;#ifdef LOCAL#define debug_flag 0#else#define debug_flag 0#endif template <class T1, class T2 >std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) { os << "[" << p.first << ", " << p.second << "]"; return os;} template <class T >std::ostream& operator << (std::ostream& os, const std::vector<T>& v) { os << "["; bool first = true; for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) { if (!first) os << ", "; first = false; os << *it; } os << "]"; return os;} template <class T >std::ostream& operator << (std::ostream& os, const std::set<T>& v) { os << "["; bool first = true; for (typename std::set<T>::const_iterator it = v.begin(); it != v.end(); ++it) { if (!first) os << ", "; first = false; os << *it; } os << "]"; return os;}#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }vector<string> _split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.emplace_back(x); return v;}void _print(vector<string>::iterator) {}template<typename T, typename... Args>void _print(vector<string>::iterator it, T a, Args... args) { string name = it -> substr((*it)[0] == ' ', it -> length()); if (isalpha(name[0])) cerr << name << " = " << a << " "; else cerr << name << " "; _print(++it, args...);}typedef long long int int64;const int N = (int)2e5 + 100;const int ALP = 130;//build sa with empty suffixstruct SuffixArray{ int n; string str; vector<int> sa; vector<int> rev_sa; int first_pos_by_char[ALP]; int pref_sum[ALP][N]; SuffixArray() { } SuffixArray(string _str) { str = _str; n = (int)str.length(); build(); } int add(int a, int b, int m) { a += b; return a < m ? a : a - m; } void build() { int tmp[5][N]; int cnt[N]; int *pos = tmp[0]; int *arr = tmp[1], *narr = tmp[2]; int *col = tmp[3], *ncol = tmp[4]; str += " "; n++; int classes = 0; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; i++) { cnt[(int)str[i]]++; classes = max(classes, str[i] + 1); } pos[0] = 0; for (int i = 1; i < classes; i++) pos[i] = pos[i - 1] + cnt[i - 1]; for (int i = 0; i < n; i++) { col[i] = str[i]; arr[pos[col[i]]++] = i; } pos[0] = 0; for (int i = 1; i < classes; i++) pos[i] = pos[i - 1] + cnt[i - 1]; for (int shift = 1; shift < n; shift *= 2) { for (int i = 0; i < n; i++) { int npos = arr[i] - shift; if (npos < 0) npos += n; narr[pos[col[npos]]++] = npos; } pos[0] = 0; ncol[narr[0]] = 0; for (int i = 1; i < n; i++) { ncol[narr[i]] = ncol[narr[i - 1]]; if (col[narr[i]] != col[narr[i - 1]] || col[add(narr[i], shift, n)] != col[add(narr[i - 1], shift, n)]) pos[++ncol[narr[i]]] = i; } swap(col, ncol); swap(arr, narr); if (col[arr[n - 1]] == n - 1) break; } sa.resize(n); rev_sa.resize(n); for (int i = 0; i < n; i++) { sa[i] = arr[i]; rev_sa[arr[i]] = i; } str.pop_back(); n--; memset(pref_sum, 0, sizeof(pref_sum)); for (int i = 0; i <= n; i++) { int suf_ind = sa[i]; if (suf_ind == 0) continue; char char_before = str[suf_ind - 1]; pref_sum[(int)char_before][i]++; } for (int c = 0; c < ALP; c++) for (int i = 1; i < N; i++) pref_sum[c][i] += pref_sum[c][i - 1]; fill(first_pos_by_char, first_pos_by_char + ALP, -1); for (int i = 0; i <= n; i++) { int suf_ind = sa[i]; if (suf_ind == n) continue; char cur_char = str[suf_ind]; if (first_pos_by_char[(int)cur_char] == -1) first_pos_by_char[(int)cur_char] = i; } }};struct Point{ int x, y; Point() : x(), y() {} Point(int _x, int _y) : x(_x), y(_y) {}};std::ostream& operator << (std::ostream& os, const Point &p) { os << "(" << p.x << ", " << p.y << ")"; return os;}const int ADD_TYPE = 0;const int QUERY_TYPE = 1;struct Event{ int x, type, id; int y1, y2, sign; Event() : x(), type(), id(), y1(), y2(), sign() {} Event(int _x, int _type, int _id, int _y1, int _y2, int _sign) : x(_x), type(_type), id(_id), y1(_y1), y2(_y2), sign(_sign) {} bool operator < (const Event & other) const { if (x != other.x) return x < other.x; return type < other.type; }};struct Fenwick{ int sum[N]; Fenwick() { fill(sum, sum + N, 0); } void add_val(int pos, int val) { for (int i = pos; i < N; i |= (i + 1)) sum[i] += val; } int get_sum(int a) { int res = 0; for (int i = a; i >= 0; i = (i & (i + 1)) - 1) res += sum[i]; return res; } int get_sum(int a, int b) { return get_sum(b) - get_sum(a - 1); }};struct RectSolver{ vector<Event> e_list; RectSolver() { } void add_query(int id, const pair<int, int> & seg_x, const pair<int, int> & seg_y, int sign) { if (seg_x.first == -1 || seg_y.first == -1) return; e_list.push_back(Event(seg_x.first - 1, QUERY_TYPE, id, seg_y.first, seg_y.second, -sign)); e_list.push_back(Event(seg_x.second, QUERY_TYPE, id, seg_y.first, seg_y.second, sign)); } void solve(const vector<Point> & points, int ans[]) { for (Point p : points) e_list.push_back(Event(p.x, ADD_TYPE, 0, p.y, p.y, 0)); sort(e_list.begin(), e_list.end()); Fenwick fenwick; for (Event e : e_list) { if (e.type == ADD_TYPE) { fenwick.add_val(e.y1, 1); } else { int sum = fenwick.get_sum(e.y1, e.y2); ans[e.id] += sum * e.sign; } } }};string next_token(){ char buf[N]; scanf("%s", buf); return string(buf);}string reversed(string s){ reverse(s.begin(), s.end()); return s;}int k;string s;string rev_s;SuffixArray direct_array;SuffixArray reverse_array;vector<Point> k_points;vector<Point> k1_points;RectSolver k_solver, k1_solver;int ans[N];int get_sum(const int pref_sum[], int l, int r){ if (l > r) return 0; int res = pref_sum[r]; if (l != 0) res -= pref_sum[l - 1]; return res;}vector<pair<int, int> > get_segs(const SuffixArray & array, const string & pattern){ dbg(array.n, array.str, array.sa, array.rev_sa, pattern); int pat_len = pattern.length(); vector<pair<int, int> > seg_list(pat_len, make_pair(-1, -1)); int cur_l = 0; int cur_r = array.n; dbg(cur_l, cur_r); for (int i = pat_len - 1; i >= 0; i--) { char pat_c = pattern[i]; int seg_sum = get_sum(array.pref_sum[(int)pat_c], cur_l, cur_r); if (seg_sum == 0) break; int sum_before = get_sum(array.pref_sum[(int)pat_c], 0, cur_l - 1); int new_l = array.first_pos_by_char[(int)pat_c] + sum_before; int new_r = new_l + seg_sum - 1; dbg(i, seg_sum, sum_before, new_l, new_r); seg_list[i] = make_pair(new_l, new_r); cur_l = new_l; cur_r = new_r; } dbg(seg_list); dbg("---"); return seg_list;}void solve(int id, const string & pattern){ if (k > (int)pattern.length()) { ans[id] = max(0, (int)s.length() - (int)pattern.length() + 1); return; } vector<pair<int, int> > direct_seg_list = get_segs(direct_array, pattern); vector<pair<int, int> > reverse_seg_list = get_segs(reverse_array, reversed(pattern)); reverse(reverse_seg_list.begin(), reverse_seg_list.end()); dbg(pattern, direct_seg_list, reverse_seg_list); for (int i = 0; i + k - 1 < (int)pattern.length(); i++) { pair<int, int> x_seg = make_pair(0, (int)s.length()); pair<int, int> y_seg = make_pair(0, (int)s.length()); if (i - 1 >= 0) y_seg = reverse_seg_list[i - 1]; if (i + k < (int)pattern.length()) x_seg = direct_seg_list[i + k]; pair<int, int> sh_y_seg = reverse_seg_list[i]; k_solver.add_query(id, x_seg, y_seg, 1); if (i + k != (int)pattern.length()) k1_solver.add_query(id, x_seg, sh_y_seg, -1); }}int main(){#ifdef LOCAL freopen ("input.txt", "r", stdin);#endif scanf("%d", &k); s = next_token(); rev_s = reversed(s); direct_array = SuffixArray(s); reverse_array = SuffixArray(rev_s); dbg(direct_array.n, direct_array.str, direct_array.sa); for (int l = 0; l < (int)s.length(); l++) { int r = l + k - 1; if (r >= (int)s.length()) break; int x = 0; int y = 0; if (l - 1 >= 0) { int rev_i = l - 1; rev_i = (int)s.length() - 1 - rev_i; y = reverse_array.rev_sa[rev_i]; } if (r + 1 < (int)s.length()) x = direct_array.rev_sa[r + 1]; int new_rev_i = l; new_rev_i = (int)s.length() - 1 - new_rev_i; int new_y = reverse_array.rev_sa[new_rev_i]; k_points.push_back(Point(x, y)); k1_points.push_back(Point(x, new_y)); } dbg(k_points); dbg(k1_points); int p_cnt; scanf("%d", &p_cnt); for (int i = 0; i < p_cnt; i++) { string pat = next_token(); solve(i, pat); } k_solver.solve(k_points, ans); k1_solver.solve(k1_points, ans); for (int i = 0; i < p_cnt; i++) printf("%dn", ans[i]); return 0;} coding problems