[Spoj] SUBLEX - Lexicographical Substring Search

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : SUBLEX - Lexicographical Substring Search
Source            : Spoj
Category          : String
Algorithm         : Suffix Automaton
Verdict           : Accepted 

#include <bits/stdc++.h>
 
using namespace std;
 
#define ff              first
#define ss              second
 
const int mx = 9e4+5;
 
struct state 
{
     int len;
     int link;
     map <char, int> next;
} st[mx << 1];
 
int sz, last;
 
void init()
{
      sz = last = 0;
      st[0].len = 0;
      st[0].link = -1;
      ++sz;
}
 
void sa_extend(char c)
{
      int curr = sz++;
      st[curr].len = st[last].len + 1;
      int p;
      for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
            st[p].next[c] = curr;
      if (p == -1)
            st[curr].link = 0;
      else
      {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len)
                  st[curr].link = q;
            else
            {
                  int clone = sz++;
                  st[clone].len = st[p].len + 1;
                  st[clone].next = st[q].next;
                  st[clone].link = st[q].link;
                  for ( ; p != -1 && st[p].next[c] == q; p = st[p].link)
                        st[p].next[c] = clone;
                  st[q].link = st[curr].link = clone;
            }
      }
      last = curr;
}
 
int dp[mx << 1];
 
int dfs(int ver)
{
      if (dp[ver]) return dp[ver];
      int tp = 1;
      for (auto it : st[ver].next)
      {
             tp += dfs(it.ss);
      }
      return dp[ver] = tp;
}
 
void kLex(int ver, int k)
{
      if (k == 0) return;
      for (auto it : st[ver].next)
      {
            int tSub = dp[it.ss];
            if (tSub < k) // this state node belong
            {
                  k -= tSub;
            }
            else
            {
                  cout << it.ff;
                  if (k == 1) cout << endl;
                  kLex(it.ss, k-1);
                  return; // do nothing when return
            }
      }
}
 
int main()
{
      ios::sync_with_stdio(0);
      cin.tie(nullptr);
 
      string s;
      cin >> s;
      int len = s.length();
      init();
      for (int f=0; f<len; f++)
      {
            sa_extend(s[f]);
      }
      dfs(0);
      int q;
      cin >> q;
      while (q--)
      {
            int k;
            cin >> k;
            kLex(0, k);
      }
}