Longest Common Substring Suffix Array

#include <bits/stdc++.h>

using namespace std;

void CountingSort (vector < int > &P, vector < int > C) {
  int N = P.size();
  vector < int > freq(N, 0);
  for (auto it : C)
  freq[it] ++;
  vector < int > P_New (N, 0), poz (N, 0);
  for (int i = 1; i < N; i ++)
  poz[i] = poz[i - 1] + freq[i - 1];
  for (auto it : P) {
    P_New[poz[C[it]]] = it;
    poz[C[it]] ++;
  }
  P = P_New;
}

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  string s1, s2, s;
  cin >> s1 >> s2;
  int lg = s1.size();
  for (int i = 0; i < lg; i ++)
  s.push_back(s1[i]);
  s.push_back('$');
  lg = s2.size();
  for (int i = 0; i < lg; i ++)
  s.push_back(s2[i]);
  s.push_back('#');
  int N = s.size();
  lg = s1.size();
  vector < int > P(N), C(N);
  vector < pair < char , int > > a(N);
  for (int i = 0; i < N; i ++)
  a[i] = {s[i], i};
  sort (a.begin(), a.end());
  for (int i = 0; i < N; i ++)
  P[i] = a[i].second;
  C[P[0]] = 0;
  for (int i = 1; i < N; i ++)
  if (a[i].first == a[i - 1].first)
  C[P[i]] = C[P[i - 1]];
  else
  C[P[i]] = C[P[i - 1]] + 1;
  int k = 0;
  while ((1 << k) < N) {
    for (int i = 0; i < N; i ++)
    P[i] = (P[i] - (1 << k) + N) % N;
    CountingSort (P, C);
    vector < int > C_New (N, 0);
    for (int i = 1; i < N; i ++) {
      pair < int , int > Prev = {C[P[i - 1]], C[(P[i - 1] + (1 << k)) % N]},
                         Now = {C[P[i]], C[(P[i] + (1 << k)) % N]};
      if (Now == Prev)
      C_New[P[i]] = C_New[P[i - 1]];
      else
      C_New[P[i]] = C_New[P[i - 1]] + 1;
    }
    C = C_New;
    k ++;
  }
  vector < int > LCP (N);
  k = 0;
  for (int i = 0; i < N - 1; i ++) {
    int pi = C[i],
        j = P[pi - 1];
    while (s[i + k] == s[j + k])
    k ++;
    LCP[pi] = k;
    k = max (k - 1, 0);
  }
  vector < int > Class (N);
  for (int i = 0; i < N; i ++)
  if (P[i] < lg)
  Class[i] = 1;
  else
  Class[i] = 2;
  int ans = 0, poz;
  for (int i = 1; i < N; i ++)
  if (Class[i] != Class[i - 1]) {
    if (LCP[i] > ans) {
      ans = LCP[i];
      poz = P[i];
    }
  }
  for (int i = poz; i < poz + ans; i ++)
  cout << s[i];
  return 0;
}