话说上次发了一篇文章..A掉了2774这道水题，但是！用的是O(nlog^2 n)做法，有些不服..

于是本人又研究了一次后缀数组的O(nlog n)做法，终于在昨晚领悟了！特A一题..终于可以教会师弟师妹们这一种数据结构了..哭

直接上代码吧..
[code lang="cpp"]Source Code
/*
Problem: 2774 User: aclolicon
Memory: 5212K Time: 610MS
Language: G++ Result: Accepted
Source Code*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 200500
using namespace std;
char s[MAXN], s2[MAXN];
int n, len;
int sa[MAXN], c[MAXN], t[MAXN], t2[MAXN], rank[MAXN], height[MAXN];
void buildsa(){
int *x = t, *y = t2, m = 300;
memset(c, 0, sizeof(c));

for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
for (int k = 1; k <= n; k *= 2){
int p = 0;
for (int i = n - k; i < n; i++) y[p++] = i;
for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
memset(c, 0, sizeof(c));
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] =y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (int i = 1; i < n; i++) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])? p - 1: p++;
if (p >= n) break;
m = p;
}
}

void geth(){
n = strlen(s);
for (int i = 0; i <= n; i++) rank[sa[i]] = i;
int h = 0;
height[0] = 0;
for (int i = 0; i < n; i++){
int j = sa[rank[i] - 1];
if (h > 0) h--;
for (; j + h < n && i + h < n; h++){
if (s[j + h] != s[i + h]) break;
}
height[rank[i] - 1] = h;
}
}
int main(){
while(scanf("%s", s) > 0){
scanf("%s", s2) > 0;
len = strlen(s2);
n = strlen(s);
if (s2 > s) swap(s, s2);
s[len] = '$';
for (int i = len + 1; i < len + n + 1; i++) s[i] = s2[i - len - 1];
n = strlen(s) + 1;
buildsa();
geth();
int maxh = -1;
for (int i = 0; i < n; i++){
if((sa[i] < len) != (sa[i + 1] < len)){
maxh = max(maxh, height[i]);
}
}
printf("%d", maxh);
}
}[/code]