[Light OJ] 1347 - Aladdin and the Magical Lamp

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1347 - Aladdin and the Magical Lamp
Source            : Light Online Judge
Category          : String,
Algorithm         : Suffix Automata, Longest Common Substring of 3 strings
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int inf = 1 << 28;
static const int maxn = 5000 + 5;
 
struct state
{
    int len;
    int link;
    int w;
    int v;
    map <char, int> next;
    state()
    {
          len = 0;
          link = 0;
          w = 0;
          v = 0;
          next.clear();
    }
} st[maxn << 1];
 
int sz, last;
 
inline void init()
{
    last = sz = 0;
    st[0].len = 0;
    st[0].link = -1;
    st[0].w = inf;
    st[0].v = 0;
    st[0].next.clear();
    for (int i = 1; i < (maxn << 1); i++) st[i] = state();
    ++sz;
}
 
inline void sz_extend(char c)
{
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    st[cur].w = inf;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
    {
        st[p].next[c] = cur;
    }
    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].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[cur].link = clone;
        }
    }
    last = cur;
}
 
int tNode; // maximum length among 3 strings
 
inline void buildDFA(string s, int len)
{
    init();
    for (int i = 0; i < len; i++) sz_extend(s[i]);
    tNode = sz;
}
 
inline 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[4];
int arr_len[4];
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        int n = 3;
        int m = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
            arr_len[i] = arr[i].length();
            if (arr_len[i] >= arr_len[m]) m = i;
        }
        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));
        }
        printf("Case %d: %d\n", tcase, res);
    }
    return 0;
}