longest common sub string(suffix array)

/*
======================
[     ___T_          ]
[    | 6=6 | =>HI :-)]
[    |__o__|         ]
[ >===]__o[===<      ]
[     [o__]          ]
[      .".           ]
[      |_|           ]
[                    ]
======================
*/

#include <bits/stdc++.h>
using namespace std;

vector<int> sort_cyclic_shifts (string const& s) {
    int n = (int) s.size();
    const int alphabet = 256;
    vector<int> p(n),c(n),cnt(max(alphabet,n),0);
    for (int i = 0; i < n; ++i) ++cnt[s[i]];
    for (int i = 1; i < alphabet; ++i) cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; ++i) p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; ++i) {
        if (s[p[i]] != s[p[i - 1]]) ++ classes;
        c[p[i]] = classes - 1;
    }
    vector<int> pn(n),cn(n);
    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.begin(),cnt.begin() + classes,0);
        for (int i = 0; i < n; ++i) ++cnt[c[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[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; ++i) {
            pair<int,int> cur = make_pair(c[p[i]],c[(p[i] + (1 << k)) % n]);
            pair<int,int> prev = make_pair(c[p[i - 1]],c[(p[i - 1] + (1 << k)) % n]);
            if (cur != prev) ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> lcp_construction (string const& s,vector<int> const& p) {
    int n = (int) s.size();
    vector<int> rank(n,0);
    for (int i = 0; i < n; ++i) rank[p[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 = p[rank[i] + 1];
        while (i + k < n and j + k < n and s[i + k] == s[j + k]) ++k;
        lcp[rank[i]] = k;
        if (k) --k;
    }
    return lcp;
}

vector<int> suffix_array_construction (string s) {
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         string s,t;
         cin >> s >> t;
         int n = (int) s.size();
         s += '#' + t + '$';
         vector<int> p = suffix_array_construction(s);
         vector<int> lcp = lcp_construction(s,p);
         int max_length = 0;
         string res = "";
         for (int i = 1; i < (int) s.size(); ++i) {
             if ((p[i] < n and p[i - 1] > n) or (p[i] > n and p[i - 1] < n)) {
                 max_length = max(max_length,lcp[i - 1]);
                 if ((int) res.size() < max_length) {
                     res = s.substr(p[i - 1],max_length);
                 }
             }
         }
         cout << res << "\n";
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}