[POJ] 2774 - Long Long Message

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 2774 - Long Long Message
Source            : POJ
Category          : String
Algorithm         : Suffix Automaton
Verdict           : Accepted 
Problem Type : Longest Common Substring of 2 string.
               Array Implemetation.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
 
using namespace:: std;

const int mx = 1e5+5; 

struct state {
    int len, link;
    //map <char, int> next;  // cause TLE
    int next[27];
    state() 
    {
        len = 0;
        link = -1;
        memset(next, 0, sizeof(next));
    }
};
 
state 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(int c)
{
    int curr = sz++;
    st[curr].len = st[last].len + 1;
    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].next = st[q].next;
            for (int i = 0; i < 27; i++) st[clone].next[i] = st[q].next[i];
            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;
}
 
char s[mx], t[mx];
 
void LCS()
{
    init();
    int len_s = strlen(s);
    int len_t = strlen(t);
    for (int i = 0; i < len_s; i++) sz_extend(s[i] - 'a');
    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[t[i] - 'a'])
        {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next[t[i] - 'a'])
        {
            v = st[v].next[t[i] - 'a'];
            l++;
        }
        if (l > best)
        {
            best = l;
            bestPos = i;
        }
    }
    printf("%d\n", best);
}
 
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    scanf("%s%s", s, t);
    LCS();
}