[Spoj] LCS2 - Longest Common Substring II

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

#include <bits/stdc++.h>
 
using namespace std;
 
 
const int inf = 1 << 17;
const int mx = 5e5+5;
 
struct state 
{
    int len;
    int link;
    int w;
    int v;
    int next[27];
} st[mx << 1];
 
int sz, last;
 
void init()
{
    last = sz = 0;
    st[0].len = 0;
    st[0].link = -1;
    st[0].w = inf;
    st[0].v = 0;
    for (int i = 0; i < 26; i++) st[0].next[i] = 0;
    ++sz;
}
 
void sz_extend(int c)
{
    int curr = sz++;
    st[curr].len = st[last].len + 1;
    st[curr].w = inf;
    int p;
    for (p = last; p != -1 && !st[p].next[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].link = st[q].link;
            for (int i = 0; i < 27; i++) st[clone].next[i] = st[q].next[i];
            st[clone].w = inf;
            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 tNode;
 
void buildDFA(string s, int len)
{
    init();
    for (int f=0; f<len; f++)
        sz_extend(s[f] - 'a');
    tNode = sz;
}
 
void LCS(string t, int len)
{
    int v = 0;
    int l = 0;
    for (int i=0; i<len; i++)
    {
        int c = t[i] - 'a';
        while (v && !st[v].next[c])
        {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next[c])
        {
            v = st[v].next[c];
            l++;
        }
        st[v].v = max(st[v].v, l);
    }
    for (int i=1; i<tNode; i++)
        st[st[i].link].v = max(st[st[i].link].v, st[i].v);
    for (int i=0; i<tNode; i++)
    {
        st[i].w = min(st[i].w, st[i].v);
        st[i].v = 0;
    }
}
 
string arr[12];
int arr_len[12];

int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int index = 0;
    int m = 0;
 
    while (cin >> arr[index])
    {
        arr_len[index] = arr[index].length();
        if (arr_len[index] > arr_len[m])
            m = index;
        index++;
    }
    buildDFA(arr[m], arr_len[m]);
    for (int i=0; i<index; i++)
    {
        if (i == m) continue;
        LCS(arr[i], arr_len[i]);
    }
    int res = -1;
    for (int i=0; i<tNode; i++)
    {
        res = max(res, min(st[i].len, st[i].w));
    }
    cout << res << endl;
}