bleh

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

struct state
{
    int len, link;
    map<char, int> next;
};

struct result
{
    int bestpos;
    string match;
};

const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz = 0, last;

string reverse_complement(string T)
{
    reverse(T.begin(), T.end());
    for (int i = 0; i < T.length(); i++)
    {
        switch (T[i])
        {
        case 'A':
            T[i] = 'T';
            break;
        case 'T':
            T[i] = 'A';
            break;
        case 'G':
            T[i] = 'C';
            break;
        case 'C':
            T[i] = 'G';
            break;
        }
    }

    return T;
}
void sa_init()
{
    st[0].len = 0;
    st[0].link = -1;
    cout << "sz: " << sz << endl;
    sz++;
    last = 0;
}

void sa_extend(char c)
{
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next.count(c))
    {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1)
    {
        st[cur].link = 0;
    }
    else
    {
        int q = st[p].next[c];
        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;
            while (p != -1 && st[p].next[c] == q)
            {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

result lcs(string S, string T)
{
    sa_init();
    for (int i = 0; i < S.size(); i++)
        sa_extend(S[i]);

    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < T.size(); i++)
    {
        while (v && !st[v].next.count(T[i]))
        {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(T[i]))
        {
            v = st[v].next[T[i]];
            l++;
        }
        if (l > best)
        {
            best = l;
            bestpos = i;
        }
    }

    result res;
    res.bestpos = bestpos - best + 1;
    res.match = T.substr(bestpos - best + 1, best);
    return res;
}

int main()
{
    // your code goes here
    string s = "ATCAACATCATAGCCAGATGCCCAGAGATTAGAGCGCATGACAAGTAAAGGACGGTTGTCAGCGTCATAAGAGGTTTTACCTCCAAATGAAGAAATAACATCATGGTAACGCTGCATGAAGTAATCACGTTCTTGGTCAGTATGCAAATTAGCATAAGCAGCTTGCAGACCCATAATGTCAATAGATGTGGTAGAAGTCGTCATTTGGCGAGAAAGCTCAGTCTCAGGAGGAAGCGGAGCAGTCCAAATG";
    string t = "AGCGCCGTGGATGCCTGACCGTACCGAGGCTAACCCTAATGAGCTTAATCAAGATGATGCTCGTTATGGTTTCCGTTGCTGCCATCTCAAAAACATTTGGACTGCTCCGCTTCCTCCTGAGACGGAGCTTTCTCGCCACATGACGACTTCTACCACATCTATTGACATTATGGGTCTGCAAGCTGCTTATGCTAATTTGCATACTGACCAAGAACGTGATTACTTCATGCAGCGTTACCATGCTGTAATT";
    t = reverse_complement(t);
    result res1 = lcs(s, t);
    for (int i = 0; i < sz; i++)
        st[i].next.clear();
    result res2 = lcs(t, s);

    int headpos1 = res1.bestpos;
    int headpos2 = res2.bestpos;
    int endpos1 = headpos1 + res1.match.size();
    int endpos2 = headpos2 + res2.match.size();
    cout << res1.bestpos << "\n"
         << res1.match << endl;
    cout << res2.bestpos << "\n"
         << res2.match << endl;

    return 0;
}