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:
  1. |s| = |r|;
  2. or all i and j such that si != ri and sj != rj, it holds |i - j| < k.


HackerEarth One mismatch problem solution


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 suffix

struct 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("%d\n", ans[i]);

return 0;
}