SPOJ::LCS2 - Longest Common Substring II

LCS2 problem can be solved by using SuffixAutomata a.k.a DAWG. I have written a small writeup on DAWGshere. I suggest you to go through it, if you are not comfortable with DAWGs.

// =====================================================================================
//    Description:
//         Author:  BrOkEN@!
// =====================================================================================
 
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
 
using namespace std;
 
template< class T > inline T _maxOfThree(T a,T b,T c) {return max(max(a,b),c);}
template< class T > inline T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _square(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool in_range(T x, T i, T y) { return x<=i && i<=y; }
 
 
#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define REV_FOR(i,a,b) for(typeof((a)) i=(a); i >= (b) ; --i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)
#define REV_FOREACH(it,x) for(typeof((x).rbegin()) it=(x).rbegin(); it != (x).rend() ; ++it)
#define SET(p, v) memset(p, v, sizeof(p))
#define CPY(p, v) memcpy(p, v, sizeof(p))
#define CLR(p) SET(p,0)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ARRAY_SIZE(array) (sizeof(array) / sizeof((array)[0]))
#define __int64 long long
 
typedef pair<int,int> PI;
typedef vector<PI> VI;
 
const int ALPHA_MAX = 26;
const int MAX = 201000;
 
typedef struct state{
    int length;
    state* link;
    state* next[ALPHA_MAX];
    int lcs,nlcs;
} state;
 
 
    int total=0;
    state pool[MAX<<1];
    state* tpool[MAX<<1];
    int counts[MAX];
   
    state* head;
    state* last;
   
    void sam_init(){
        head=last=&pool[total++];
    }
   
    void sam_track(int length){
        for(int i=0;i<total;i++) counts[pool[i].length]++; 
        for(int i=1;i<=length;i++) counts[i]+=counts[i-1]; 
        for(int i=0;i<total;i++) {    tpool[--counts[pool[i].length]]=&pool[i]; }
    }
   
    void sam_updateBests(){
        state* p=NULL;
        for(int i=total-1;i>=0;i--) {
            p=tpool[i];
            if(p->lcs<p->nlcs) p->nlcs = p->lcs;
            if(p->link && p->link->lcs<p->lcs) p->link->lcs = p->lcs;
            p->lcs =0;
        }
    }
   
    int sam_best(){
        int ans=0; 
        for(int i=0;i<total;i++) if(pool[i].nlcs>ans) ans=pool[i].nlcs;
        return ans;
    }
   
    void sam_insert(int ch,int len){
        state* curr = &pool[total++];
        curr->length = curr->nlcs = len;
       
        state* p = last;
        while(p && !p->next[ch]) p->next[ch]=curr,p=p->link;
        if(!p){
            curr->link = head;
        }else{
            state* q = p->next[ch];
           
            if(p->length +1 == q->length){
                curr->link = q;
            }else{
                state* clone = &pool[total++];
                *clone = *q; 
                clone->length = clone->nlcs = p->length +1;
               
                while(p && p->next[ch]==q) p->next[ch]=clone,p=p->link;
                curr->link = q->link = clone;
            }
        } 
        last = curr;
    }
   
    void sam_traverse(state** p,int& len,int ch){
        while(*p!=head && (*p)->next[ch]==NULL){
            *p = (*p)->link;
            len = (*p)->length;
        }
        if((*p)->next[ch]){
            *p = (*p)->next[ch];
            len++;
        }
        if(len > (*p)->lcs) (*p)->lcs = len;
    }
   
 
char A[MAX];
int lenA=0;
 
int lcs(){
    sam_init();
    scanf("%s",A);
    lenA = strlen(A);
    FOR(i,0,lenA-1) sam_insert(A[i]-'a',i+1);
    sam_track(strlen(A));
   
 
    while(scanf("%s",A)!=EOF){
     lenA = strlen(A);
        int l = 0;
        state* p = head;
        FOR(i,0,lenA-1){
            sam_traverse(&p,l,A[i]-'a');
        }
        sam_updateBests();
    }
    return sam_best();
}
 
int main(){
    printf("%d\n",lcs());
    return 0;
}