[Codeforces] B. String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : B. String
Source            : Codeforces
Category          : String
Algorithm         : Suffix Automaton, kth lexicographical substring
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e5 + 5;  
  
struct State  
{  
      int len;  
      int link;  
      long long occ;  
      long long word;  
      map <char, int> Next;  
  
      State() {}  
      void clean()  
      {  
            len = 0;  
            link = -1;  
            occ = 0;  
            word = 0;  
            Next.clear();  
      }  
} st[maxn * 2];  
  
int sz;  
int last;  
  
void init()  
{  
      sz = 0;  
      last = 0;  
      for (int i = 0; i < maxn * 2; i++) st[i].clean();  
      sz++;  
}  
  
void SAM(char ch)  
{  
      int cur = sz++;  
      st[cur].len = st[last].len + 1;  
      int p;  
      for (p = last; p != -1 && !st[p].Next.count(ch); p = st[p].link)  
      {  
            st[p].Next[ch] = cur;  
      }  
      if (p == -1)  
      {  
            st[cur].link = 0;  
      }  
      else  
      {  
            int q = st[p].Next[ch];  
            if (st[p].len + 1 == st[q].len)  
            {  
                  st[cur].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[ch] == q; p = st[p].link)  
                  {  
                        st[p].Next[ch] = clone;  
                  }  
                  st[q].link = st[cur].link = clone;  
            }  
      }  
      last = cur;  
}  
  
void allTerminal()  
{  
      int cur = last;  
      while (cur > 0)  
      {  
            st[cur].occ += 1;  
            cur = st[cur].link;  
      }  
}  
  
void dfs(int u = 0)  
{  
      if (st[u].word) return;  
      for (auto it : st[u].Next)  
      {  
            int v = it.second;  
            dfs(v);  
            st[u].occ += st[v].occ;  
            st[u].word += st[v].word;  
      }  
      st[u].word += st[u].occ;  
}  
  
void kthLex(int u, int k, string &s)  
{  
      if (k <= 0) return;  
      for (auto it : st[u].Next)  
      {  
            int v = it.second;  
            if (st[v].word >= k)  
            {  
                  s.push_back(it.first);  
                  return void(kthLex(v, k - st[v].occ, s));  
            }  
            else  
            {  
                  k -= st[v].word;  
            }  
      }  
}  
  
int 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;  
      int k;  
      cin >> s >> k;  
      init();  
      for (char ch : s) SAM(ch);  
      allTerminal();  
      dfs();  
      string ans;  
      kthLex(0, k, ans);  
      if (ans.empty()) ans = "No such line.";  
      cout << ans << endl;  
}