[UVa Live Archive] 3451 - Longest Common Substring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 3451 - Longest Common Substring
Source            : UVa Live Archive
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 << 28;  
const int mx = 1e5+5;  
   
struct state   
{  
    int len;  
    int link;  
    int w;  
    int v;   
    map <char, int> next;  
} 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 < (mx << 1); i++) st[i].next.clear();  
    ++sz;  
}  
   
void sz_extend(char 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.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].link = st[q].link;  
            st[clone].next = st[q].next;  
            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]);  
    tNode = sz;  
}  
   
void LCS(string t, int len)  
{  
    int v = 0;  
    int l = 0;  
    for (int i = 0; i < len; i++)  
    {  
        char c = t[i];  
        while (v && !st[v].next.count(c))  
        {  
            v = st[v].link;  
            l = st[v].len;  
        }  
        if (st[v].next.count(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[32];  
int arr_len[32];  
   
int main()  
{  
    //freopen("in.txt", "r", stdin);  
   
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
   
    int n;  
    while (cin >> n)  
    {  
        int m = 0;  
        for (int index=0; index<n; index++)  
        {  
            cin >> arr[index];  
            arr_len[index] = arr[index].length();  
            if (arr_len[index] > arr_len[m]) m = index;  
        }  
        buildDFA(arr[m], arr_len[m]);  
        for (int i = 0; i < n; 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;  
    }  
    return 0;  
}