[Spoj] LCS - Longest Common Substring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : LCS - Longest Common Substring
Source            : Spoj
Category          : String
Algorithm         : Suffix Automaton
Verdict           : Accepted 
Problem Type : Longest Common Substring of 2 string.

#include <bits/stdc++.h>
 
using namespace std;
 
const int mx = 250000 + 5;
 
struct state 
{
    int len, link;
    map <char, int> next;
}st[mx << 1];
 
int sz, last;
 
void init()
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
 
    //clear the structure
    //for (int i=0; i<(mx<<1); i++)
    //{
    //    st[i].next.clear();
    //}
}
  
void sz_extend(char c)
{
    int curr = sz++; 
    st[curr].len = st[last].len + 1;
    int p;
    for (p=last; p != -1 && !st[p].next.count(c); p = st[p].link)
        st[p].next[c] = curr;
    if (p == -1)
        st[curr].link = 0;
    else
    {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len)
            st[curr].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[c] == q; p = st[p].link)
                st[p].next[c] = clone;
            st[q].link = st[curr].link = clone;
        }
    }
    last = curr;
}
 
 
int LCS(string s, string t)
{
    init();
    int len_s = s.length();
    int len_t = t.length();
    for (int i=0; i<len_s; i++)
    {
        sz_extend(s[i]);
    }
    int v = 0;
    int l = 0;
    int best = 0;
    int bestPos = 0;
    for (int i=0; i<len_t; 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;
        }
    }
    //return t.substr(bestPos-best+1, best); // LCS
    return best;
}
 
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;
    cout << LCS(s, t) << endl;
}