HackerEarth Little Shino and Substring Query problem solution

In this HackerEarth Little Shino and Substring Query problem solution, we have given N words and Q queries. Each query will have a string. You have to print two integers. Index of lexicographical smallest and largest string that contains the query string as substring. If there are multiple lexicographical smallest string, print the smallest index. If there are multiple lexicographical largest string, print the largest index. If there is no word that contains the query string as substring, print 1.

HackerEarth Little Shino and Substring Query problem solution.

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define pi 3.141592653589793

using namespace std;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }

typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;

const int MOD = 1e9 + 7;
const int INF = 1e9;
// Template End
const int MAX = 2000005;
char T[MAX], s[MAX];
int n, RA[MAX], SA[MAX], m, posi[MAX], ran[MAX], h[MAX];
int tempRA[MAX], tempSA[MAX], c[MAX];
char W[MAX];
vector <pair<string, int> > v;
PII tree[4*MAX];


void countingSort(int k)
{
    int sum = 0, maxi = max(300, n), t;
    REP(i, 0, MAX, 1) c[i] = 0;
    REP(i, 0, n, 1) c[(i+k) < n ? RA[i+k] : 0]++;
    REP(i, 0, maxi, 1)
    {
        t = c[i];
        c[i] = sum;
        sum += t;
    }
    REP(i, 0, n, 1) tempSA[c[(SA[i] + k) < n ? (RA[SA[i] + k]) : 0]++] = SA[i];
    REP(i, 0, n, 1) SA[i] = tempSA[i];
}

void constructSA()
{
    int k, r;
    REP(i, 0, n, 1) RA[i] = T[i], SA[i] = i;
    for(k = 1;k < n;k <<= 1)
    {
        countingSort(k);
        countingSort(0);
        tempRA[SA[0]] = r = 0;
        REP(i, 1, n, 1)
            tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] and RA[SA[i] + k] == RA[SA[i-1] + k]) ? r : ++r;
        REP(i, 0, n, 1) RA[i] = tempRA[i];
        if(RA[SA[n-1]] == n-1) break;
    }
}

PII stringMatching()
{
    int lo = 0, hi = n-1, mid = lo;
    while(lo < hi)
    {
        mid = (lo + hi) / 2;
        int res = strncmp(T + SA[mid], s, m);
        if(res >= 0) hi = mid;
        else lo = mid + 1;
    }
    if(strncmp(T + SA[lo], s, m) != 0) return {-1, -1};
    PII ans;
    ans.fi = lo;
    lo = 0, hi = n-1, mid = lo;
    while(lo < hi)
    {
        mid = (lo + hi) / 2;
        int res = strncmp(T + SA[mid], s, m);
        if(res > 0) hi = mid;
        else lo = mid + 1;
    }
    if(strncmp(T + SA[hi], s, m) != 0) hi--;
    ans.se = hi;
    return ans;
}

PII merge(PII a, PII b)
{
    PII p;
    p.fi = min(a.fi, b.fi);
    p.se = max(a.se, b.se);
    return p;
}

void build(int node, int start, int end)
{
    if(start == end)
    {
        tree[node].fi = ran[h[SA[start]]];
        tree[node].se = ran[h[SA[start]]];
    }
    else
    {
        int mid = (start + end) >> 1;
        int left = node << 1;
        int right = left + 1;
        build(left, start, mid);
        build(right, mid+1, end);
        tree[node] = merge(tree[left], tree[right]);
    }
}

PII query(int node, int start, int end, int l, int r)
{
    if(l <= start and end <= r) return tree[node];
    if(end < l or r < start) return mp(INF, -1);
    int left = node << 1;
    int right = left + 1;
    int mid = (start + end) >> 1;
    PII p1 = query(left, start, mid, l, r);
    PII p2 = query(right, mid+1, end, l, r);
    return merge(p1, p2);
}

int main(int argc, char* argv[])
{
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    int N, Q;
    PII pos;
    scanf("%d %d", &N, &Q);
    posi[0] = 0;
    REP(i, 0, N, 1)
    {
        scanf("%s", s);
        v.pb(mp(s, i));
        h[posi[i]] = i;
        posi[i+1] =  posi[i] + strlen(s) + 1;
        REP(j, posi[i]+1, posi[i+1], 1) h[j] = h[j-1];
        strcat(T, s);
        strcat(T, "$");
    }
    n = strlen(T);
    constructSA();

    sort(all(v));
    REP(i, 0, N, 1) ran[v[i].se] = i;
    build(1, 0, n-1);
    REP(i, 1, Q+1, 1)
    {
        scanf("%s", s);
        m = strlen(s);
        pos = stringMatching();
        if(pos.fi != -1 and pos.se != -1)
        {
            PII ans = query(1, 0, n-1, pos.fi, pos.se);
            printf("%d %d\n", v[ans.fi].se, v[ans.se].se);
        }
        else
        {
            printf("-1 -1\n");
        }
    }
    return 0;
}