http://vjudge.net/contest/view.action?cid=31226#overview
SPOJ LCS Longest Common Substring

SPOJ LCS2 Longest Common Substring II
http://vjudge.net/problem/viewProblem.action?id=28017

//}/* .................................................................................................................................. */

const int N = int(2e5) + 9, Z = 26;

namespace SAM{

    int trans[N][Z],par[N],len[N],tail,tot;
    char buf[N];

    int new_node(){
        RST(trans[tot]);
        return tot++;
    }
    int new_node(int u){
        CPY(trans[tot],trans[u]),par[tot]=par[u];
        return tot++;
    }
#define v trans[u][c]
#define p par[u]
#define pp par[uu]

    int Ext(int c){

        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = p;
        if (!u && !v) v = uu, pp = 0;
        else{
            if (len[v] == len[u] + 1) pp = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                par[_v] = pp = vv; while (v == _v) v = vv, u = p;
            }
        }

        return tail = uu;
    }

#define c (*cur - 'a')
#define lenn C

    void Init(){
        tail = tot = 0; new_node(), RS(buf); REP_S(cur, buf) Ext(c);
    }

    int Spell(){
        static int C[N], Q[N]; //RST(C);
        REP(i, tot) ++C[len[i]];
        REP_1(i, len[tail]) C[i] += C[i-1];
        REP(i, tot) Q[--C[len[i]]] = i;

        while (~scanf("%s", buf)){
            fill(lenn, lenn+tot, 0); int u = 0, l = 0; REP_S(cur, buf){
                while (u && !v) l = len[u = p];
                if (u = v) checkMax(lenn[u], ++l);
            }
            DWN(i, tot, 1){
                int u = Q[i]; checkMax(lenn[p], lenn[u]);
                checkMin(len[u], lenn[u]);
            }
        }
        int res = 0; FOR(u, 1, tot) checkMax(res, len[u]);
        return res;
    }

} using namespace SAM;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Init(), OT(Spell());
}

Posted by xiaodao
Category: 快晴