# 某島

… : "…アッカリ～ン . .. . " .. .
August 7, 2014

## …（ing）

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]);
}
int new_node(int u){
CPY(trans[tot],trans[u]),par[tot]=par[u];
}
#define v trans[u]
#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());
}