### Brief description :

後綴數組練習題系列啊啊，最長不重疊重複子串。

### Analyse :

…

```
/*
Author : xiaodao
Prob : POJ 1743. Musical Theme
Status : Accepted
Last modify : GMT +8. Sept 16th 11:07
Tags : Suffix Array
*/
#include
```
#include
#include
#include
using namespace std;
const int INF = 100000;
const int N = 20000, M = 88;
int SA[N], rank[N], height[N], key[N];
int A[N], C[N], t1[N+1], t2[N+1];
int n, m, ans;
void init(){
int i, j, k, l, s; int *X = t1, *Y = t2;
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;
}
}
}
bool f(int x){
int l = SA[0], r = SA[0];
for (int i=1;i= x) l = min(l, SA[i]), r = max(r, SA[i]);
else {
if (r-l >= x) return true;
l = SA[i], r = SA[i];
}
}
if (r-l >= x) return true;
return false;
}
void solve(){
if (!f(4)) ans = 0;
else {
int l=4, r=n/2, m;
while (l>n && n!=0){
init(); solve();
cout << ans << endl;
}
}