[Toph] The Story of Stringland

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : The Story of Stringland
Source            : toph.co
Category          : String, Data Structure
Algorithm         : Suffix Array, Palindromic Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e6 + 5;  
static const int logn = 20;  
  
int p[maxn];  
int pn[maxn];  
int c[logn][maxn];  
int cn[maxn];  
int cnt[maxn];  
  
void sort_cyclic_shifts(string &s)  
{  
      int n = s.size();  
      memset(cnt, 0, sizeof cnt);  
      for (int i = 0; i < n; i++) cnt[ s[i] ]++;  
      for (int i = 1; i < 256; i++) cnt[i] += cnt[i - 1];  
      for (int i = 0; i < n; i++) p[ --cnt[ s[i] ] ] = i;  
      int classes = 1;  
      for (int i = 0; i < n; i++)  
      {  
            if (i && s[ p[i] ] != s[ p[i - 1] ]) classes++;  
            c[0][ p[i] ] = classes - 1;  
      }  
      for (int k = 0; (1 << k) < n; k++)  
      {  
            for (int i = 0; i < n; i++)  
            {  
                  pn[i] = p[i] - (1 << k);  
                  if (pn[i] < 0) pn[i] += n;  
            }  
            fill(cnt, cnt + classes, 0);  
            for (int i = 0; i < n; i++) cnt[ c[k][ pn[i] ] ]++;  
            for (int i = 1; i < classes; i++) cnt[i] += cnt[i - 1];  
            for (int i = n - 1; i >= 0; i--) p[ --cnt[ c[k][ pn[i] ] ] ] = pn[i];  
            classes = 1;  
            cn[ p[0] ] = 0;  
            pair <int, int> x;  
            pair <int, int> y;  
            for (int i = 1; i < n; i++)  
            {  
                  x = {c[k][ p[i] ], c[k][(p[i] + (1 << k)) % n]};  
                  y = {c[k][ p[i - 1] ], c[k][(p[i - 1] + (1 << k)) % n]};  
                  if (x != y) classes++;  
                  cn[ p[i] ] = classes - 1;  
            }  
            for (int i = 0; i < n; i++) c[k + 1][i] = cn[i];  
      }  
}  
  
vector <int> suffix_array_construction(string s)  
{  
      s += "$";  
      sort_cyclic_shifts(s);  
      vector <int> sorted_shifts;  
      int n = s.size();  
      for (int i = 1; i < s.size(); i++) sorted_shifts.push_back(p[i]);  
      return sorted_shifts;  
}  
  
int compare(int i, int j, int substr_len, int n) // compare two equal length substring in O(1)  
{  
      // i = start index of first index  
      // j = start index of second index  
      // substr_len = length of sub-string  
      // n = length of original string  
      int k = __lg(substr_len);  
      pair <int, int> a = make_pair(c[k][i], c[k][(i + substr_len - (1 << k)) % n]);  
      pair <int, int> b = make_pair(c[k][j], c[k][(j + substr_len - (1 << k)) % n]);  
      return a == b ? 0 : a < b ? -1 : 1;  
}  
  
int longest_common_prefix(int i, int j)  
{  
      int ans = 0;  
      for (int k = logn - 1; k >= 0; k--)  
      {  
            if (c[k][i] == c[k][j])  
            {  
                  ans += (1 << k);  
                  i += (1 << k);  
                  j += (1 << k);  
            }  
      }  
      return ans;  
}  
  
vector <int> lcp_construction(string const &s, vector <int> const &suffix_array)  
{  
      int n = s.size();  
      vector <int> Rank(n, 0);  
      for (int i = 0; i < n; i++) Rank[ suffix_array[i] ] = i;  
      int k = 0;  
      vector <int> lcp(n - 1, 0);  
      for (int i = 0; i < n; i++)  
      {  
            if (Rank[i] == n - 1)  
            {  
                  k = 0;  
                  continue;  
            }  
            int j = suffix_array[ Rank[i] + 1 ];  
            while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;  
            lcp[ Rank[i] ] = k;  
            if (k) --k;  
      }  
      return lcp;  
}  
  
struct PTree  
{  
      int next[27];  
      int st;  
      int len;  
      int sufflink;  
      PTree(int st = 0, int len = 0, int sufflink = 0)  
            : st(st)  
            , len(len)  
            , sufflink(sufflink)  
            {  
                  memset(next, 0, sizeof next);  
            }  
};  
  
PTree Tree[maxn];  
int num;  
int suff;  
  
void init()  
{  
      for (int i = 0; i < maxn; i++) Tree[i] = PTree();  
      num = 2;  
      suff = 2;  
      Tree[1].len = -1; Tree[1].sufflink = 1;  
      Tree[2].len = 0; Tree[2].sufflink = 1;  
}  
  
bool addLetter(string &s, int pos)  
{  
      int cur = suff;  
      int curlen = 0;  
      int let = s[pos] - 'a';  
      while (true)  
      {  
            curlen = Tree[cur].len;  
            if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos]) break;  
            cur = Tree[cur].sufflink;  
      }  
      if (Tree[cur].next[let])  
      {  
            suff = Tree[cur].next[let];  
            return false;  
      }  
      ++num;  
      suff = num;  
      Tree[num].len = Tree[cur].len + 2;  
      Tree[num].st = pos - Tree[num].len + 1;  
      Tree[cur].next[let] = num;  
      if (Tree[num].len == 1)  
      {  
            Tree[num].sufflink = 2;  
            return true;  
      }  
      while (true)  
      {  
            cur = Tree[cur].sufflink;  
            curlen = Tree[cur].len;  
            if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos])  
            {  
                  Tree[num].sufflink = Tree[cur].next[let];  
                  break;  
            }  
      }  
      return true;  
}  
  
struct Info  
{  
      int st;  
      int ed;  
      Info(int st, int ed) : st(st), ed(ed) {}  
};  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
  
      string s;  
      cin >> s;  
      int n = s.size();  
      init();  
      for (int i = 0; i < n; i++) addLetter(s, i);  
      vector <int> suffix_array = suffix_array_construction(s);  
      vector <Info> vec;  
      for (int i = 3; i <= num; i++)  
      {  
            vec.emplace_back(Tree[i].st, Tree[i].st + Tree[i].len - 1);  
      }  
      sort(vec.begin(), vec.end(), [&](Info &A, Info &B)  
           {  
                 int len1 = A.ed - A.st + 1;  
                 int len2 = B.ed - B.st + 1;  
                 int substr_len = min(len1, len2);  
                 int val = compare(A.st, B.st, substr_len, n);  
                 if (val == 0) return len1 < len2;  
                 if (val == -1) return true;  
                 return false;  
           });  
      int q;  
      cin >> q;  
      int sze = vec.size();  
      while (q--)  
      {  
            int k;  
            cin >> k;  
            if (k > sze) cout << -1 << '\n';  
            else cout << vec[k - 1].st + 1 << ' ' << vec[k - 1].ed + 1 << '\n';  
      }  
}