Longest common substring using Suffix array

/***
 created: 2022-05-22-10.21.44
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

//O(nlgn)
vector<int> sac(string s)
{
    s += '`';
    int n = s.size();
    const int A=28;
    vector<int> p(n), c(n), cnt(max(n, A));
    for (int i = 0; i < n; ++i) cnt[s[i]-'`']++;
    for (int i = 1; i < A; ++i) cnt[i] += cnt[i-1];
    for (int i = n-1; i >=0; --i) p[--cnt[s[i]-'`']] = i;
    int rnk = 1;
    for (int i = 1; i < n; ++i)
    {
        if(s[p[i]] != s[p[i-1]])  rnk++;
        c[p[i]] = rnk-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()+rnk, 0);
        for (int i = 0; i < n; ++i) cnt[c[pn[i]]]++;
        for (int i = 1; i < rnk; ++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;
        rnk = 1;
        for (int i = 1; i < n; ++i)
        {
            int x = p[i]+(1<<k), y = p[i-1]+(1<<k);
            if(x >= n)  x -= n;
            if(y >= n)  y -= n;
            pair<int, int> cur = {c[p[i]], c[x]};
            pair<int, int> prev = {c[p[i-1]], c[y]};
            if(cur != prev) rnk++;
            cn[p[i]] = rnk-1;
        }
        c.swap(cn);
    }

    p.erase(p.begin());
    return p;
}

//kasai's alog :: O(n)

vector<int> LCP(string s, vector<int> p)
{
    int n = s.size();
    vector<int> idx(n);
    for (int i = 0; i < n; ++i) idx[p[i]] = i;
    int k = 0;
    vector<int> lcp(n-1);
    for (int i = 0; i < n; ++i)
    {
        if(idx[i]==n-1)
        {
            k = 0;
            continue;
        }
        int j = p[idx[i]+1];
        while(i+k<n and j+k<n and s[i+k]==s[j+k]) k++;
        lcp[idx[i]] = k;
        if(k) k--;
    }
    return lcp;
}

//unsigned long long int N_Different_Substrings(const vector<int> &suffixArray, const vector<int> &lcp) {
//    unsigned long long int res = suffixArray[0];
//    for (int i = 1; i < suffixArray.size(); i++) {
//        res += suffixArray[i] - lcp[i - 1];
//    }
//    return res;
//}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    string s, p,y;

    cin>>s>>p;

    y=s+'{'+p;

    vector<int>sa =sac(y);

    vector<int>lcp =LCP(y,sa);

    ll n,ans=0,in,i;

    n=s.size();

    for(i=0; i<sa.size()-1; i++)
    {
        if((sa[i]<n && sa[i+1]>n) || (sa[i]>n && sa[i+1]<n))
        {
            if(lcp[i]>ans)
            {
                ans=lcp[i];
                in=sa[i]<n?sa[i]:sa[i+1];

            }
        }
    }

    cout<<s.substr(in,ans)<<nl;

    get_lost_idiot;
}