### Brief description :

后缀数组练习题系列啊啊，最长公共子串啊啊啊。

### Analyse :

…

```
/*
Author : xiaodao
Prob : POJ 2774. Long Long Message
Status : Accepted
Last modify : GMT +8. Sept 16th 11:07
Tags : Suffix Array
*/
#include
```
#include
#include
#include
using namespace std;
const int INF = 500000;
const int N = 200000, M = 256;
int SA[N], rank[N], height[N], key[N];
int A[N], C[N], t1[N+1], t2[N+1];
string s, s1, s2;
int n, m, p, ans;
void init(){
int i, j, k, l; int *X = t1, *Y = t2;
cin >> s2; s = s1 + "$" + s2; p = s1.size(); n = s.size();
for (i=0;i=0;i--) SA[--C[X[i]]] = i;
X[n] = Y[n] = INF;
for (l=1;l= l) Y[j++] = SA[i] - l;
for (i=0;i=0;i--) SA[--C[key[i]]] = Y[i];
swap(X, Y);
X[SA[0]] = j = 0;
for (i=1;i0) k--;
if (rank[i]==0) height[0] = 0;
else {
j = SA[rank[i] - 1];
while (A[i+k]==A[j+k]) k++;
height[rank[i]] = k;
}
}
}
void solve(){
ans = 0;
for (int i=1;ians) {
if (SA[i-1] < p && SA[i] > p || SA[i-1] > p && SA[i] < p)
ans = height[i];
}
}
}
int main(){
//freopen("in.txt", "r", stdin);
while (cin >> s1){
init(); solve();
cout << ans << endl;
}
}