# HackerEarth One mismatch problem solution

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.

`#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("%d\n", ans[i]);    return 0;}`