//注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
    void dc3（int *r,int *sa,int n,int m） { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = （n+1）/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for（i=0; i<n; i++） {
    if（i%3!=0）
    wa[tbc++]=i; //tbc表示起始位置模3为1或2的后缀个数
    }
    sort（r+2,wa,wb,tbc,m）；
    sort（r+1,wb,wa,tbc,m）；
    sort（r,wa,wb,tbc,m）；
    for（p=1,rn[F（wb[0]）]=0,i=1; i<tbc; i++）
    rn[F（wb[i]）]=c0（r,wb[i-1],wb[i]）？p-1:p++;
    if（p<tbc）
    dc3（rn,san,tbc,p）；
    else {
    for（i=0; i<tbc; i++）
    san[rn[i]]=i;
    }
    //对所有起始位置模3等于0的后缀排序
    for（i=0; i<tbc; i++） {
    if（san[i]<tb）
    wb[ta++]=san[i]*3;
    }
    if（n%3==1）  //n%3==1,要特殊处理suffix（n-1）
    wb[ta++]=n-1;
    sort（r,wb,wa,ta,m）；
    for（i=0; i<tbc; i++）
    wv[wb[i]=G（san[i]）]=i;
    //合并所有后缀的排序结果，保存在sa数组中
    for（i=0,j=0,p=0; i<ta&&j<tbc; p++）
    sa[p]=c12（wb[j]%3,r,wa[i],wb[j]）？wa[i++]:wb[j++];
    for（； i<ta; p++）
    sa[p]=wa[i++];
    for（； j<tbc; p++）
    sa[p]=wb[j++];
    return;
    }
    //height[i]=suffix（sa[i-1]）和suffix（sa[i]）的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀
    void calheight（int *r,int *sa,int n） {
    int i,j,k=0;
    for（i=1; i<=n; i++）
    rank1[sa[i]]=i;
    for（i=0; i<n; height[rank1[i++]]=k）
    for（k k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++）；
    }
    int solve（int n） {
    int i,sum=0;
    for（i=1; i<=n; i++） {
    sum += n - sa[i] - height[i] ;
    }
    return sum;
    }
    /****以上模版****/
    int a[N] ;
    bool check（int *sa , int n , int mid） {
    int mx = sa ;
    int mn = sa ;
    for （int i = 2 ; i <= n ; i ++ ） {
    if（height[i] < mid） {
    mx = sa[i] ;
    mn = sa[i] ;
    } else {
    mx = max（sa[i] ,mx） ;
    mn = min（sa[i] ,mn） ;
    if（mx - mn >= mid）return 1 ;
    }
    }
    return 0 ;
    }
    int main（） {
    int n ;
    while（scanf（"%d",&n ） , n ） {
    for （int i = 0 ; i < n ; i ++ ） {
    scanf（"%d",&a[i]） ;
    }
    for （int i = 0 ; i < n - 1 ; i ++ ）r[i] = a[i + 1] - a[i] + 100 ;
    r[n - 1] = 0 ;
    n -- ;
    dc3（r ,sa ,n + 1 , 200） ;
    calheight（r , sa ,n） ;
    int r = n , l = 1 ;
    int ans = 0 ;
    while（r >= l） {
    int mid = l + r 》 1 ;
    if（check（sa , n , mid）） {
    l = mid + 1 ;
    ans = max（ans ,mid） ;
    } else r = mid - 1 ;
    }
    if（ans < 4）puts（"0"） ;
    else printf（"%d\n",ans + 1） ;
    }
    return 0 ;
    }
    例 4 :可重叠的 k 次最长重复子串（ pku3261 ）
    给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。 // 同上，也是二分
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cmath>
    #include <cstring>
    #include <queue>
    #include <set>
    #include <vector>
    #include <stack>
    #include <map>
    #include <iomanip>
    #define PI acos（-1.0）
    #define Max 2505
    #define inf 1《28
    #define LL（x） （ x 《 1 ）
    #define RR（x） （ x 《 1 | 1 ）
    #define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
    #define ll long long
    #define mem（a,b） memset（a,b,sizeof（a））
    #define mp（a,b） make_pair（a,b）
    #define PII pair<int,int>
    using namespace std;
    #define N 20005
    /****后缀数组模版****/
    #define F（x）（（x）/3+（（x）%3==1 0:tb）） //F（x）求出原字符串的suffix（x）在新的字符串中的起始位置
    #define G（x）（（x）<tb （x）*3+1:（（x）-tb）*3+2） //G（x）是计算新字符串的suffix（x）在原字符串中的位置，和F（x）为互逆运算
    int wa[N],wb[N],wv[N],WS[N];
    int sa[N*3] ;
    int rank1[N],height[N];
    int r[N*3];
    int c0（int *r,int a,int b） {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
    }
    int c12（int k,int *r,int a,int b） {
    if（k==2）
    return r[a]<r[b] || （ r[a]==r[b] && c12（1,r,a+1,b+1） ）；
    else
    return r[a]<r[b] || （ r[a]==r[b] && wv[a+1]<wv[b+1] ）；
    }
    void sort（int *r,int *a,int *b,int n,int m） {
    int i;
    for（i=0; i<n; i++）
    wv[i]=r[a[i]];
    for（i=0; i<m; i++）
    WS[i]=0;
    for（i=0; i<n; i++）
    WS[wv[i]]++;
    for（i=1; i<m; i++）
    WS[i]+=WS[i-1];
    for（i=n-1; i>=0; i--）
    b[--WS[wv[i]]]=a[i];
    return;
    }
    //注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
    void dc3（int *r,int *sa,int n,int m） { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = （n+1）/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for（i=0; i<n; i++） {
    if（i%3!=0）
    wa[tbc++]=i; //tbc表示起始位置模3为1或2的后缀个数
    }
    sort（r+2,wa,wb,tbc,m）；
    sort（r+1,wb,wa,tbc,m）；
    sort（r,wa,wb,tbc,m）；
    for（p=1,rn[F（wb[0]）]=0,i=1; i<tbc; i++）
    rn[F（wb[i]）]=c0（r,wb[i-1],wb[i]）？p-1:p++;
    if（p<tbc）
    dc3（rn,san,tbc,p）；
    else {
    for（i=0; i<tbc; i++）
    san[rn[i]]=i;
    }
    //对所有起始位置模3等于0的后缀排序
    for（i=0; i<tbc; i++） {
    if（san[i]<tb）
    wb[ta++]=san[i]*3;
    }
    if（n%3==1）  //n%3==1,要特殊处理suffix（n-1）
    wb[ta++]=n-1;
    sort（r,wb,wa,ta,m）；
    for（i=0; i<tbc; i++）
    wv[wb[i]=G（san[i]）]=i;
    //合并所有后缀的排序结果，保存在sa数组中
    for（i=0,j=0,p=0; i<ta&&j<tbc; p++）
    sa[p]=c12（wb[j]%3,r,wa[i],wb[j]）？wa[i++]:wb[j++];
    for（； i<ta; p++）
    sa[p]=wa[i++];
    for（； j<tbc; p++）
    sa[p]=wb[j++];
    return;
    }
    //height[i]=suffix（sa[i-1]）和suffix（sa[i]）的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀
    void calheight（int *r,int *sa,int n） {
    int i,j,k=0;
    for（i=1; i<=n; i++）
    rank1[sa[i]]=i;
    for（i=0; i<n; height[rank1[i++]]=k）
    for（k k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++）；
    }
    int a[N] ;
    int mx ;
    bool check（int n, int m ,int mid）{
    int cnt = 1 ;
    for （int i = 1 ; i <= n ; i ++ ）{
    if（height[i] >= mid）{
    cnt ++ ;
    if（cnt >= m）return 1 ;
    }else cnt = 1 ;
    }
    return 0 ;
    }
    int main（） {
    int n , m ;
    mx = 0 ;
    int ans = 0 ;
    scanf（"%d%d",&n , &m） ;
    for （int i = 0 ; i < n ; i ++ ）{
    scanf（"%d",&a[i]） ;
    mx = max（mx ,a[i]） ;
    }
    for （int i = 0 ; i < n ; i ++ ）r[i] = a[i] ;
    r[n] = 0 ;
    //cout 《 mx 《 endl;
    dc3（r , sa , n + 1 , mx + 1 ） ;
    calheight（r, sa ,n） ;
    // cout 《 mx 《 endl;
    int l = 1 , r = n ;
    while（r >= l）{
    int mid = r + l 》 1 ;
    if（check（n , m , mid ））{//找到连续至少m个大于mid公共前缀，更新答案。
    ans = max（ans , mid） ;
    l = mid + 1 ;
    }else r = mid - 1 ;
    }
    cout 《 ans 《 endl;
    return 0 ;
    }
    例 5 :不相同的子串的个数（ spoj694,spoj705 ）
    给定一个字符串，求不相同的子串的个数。
    [解法]:
    对于每一次新加进来的后缀 suffix（sa[k]）， 它将产生 n-sa[k]+1 个新的前缀。但是其中有
    height[k] 个是和前面的字符串的前缀是相同的。所以 suffix（sa[k]） 将 " 贡献 "
    出 n-sa[k]+1- height[k] 个不同的子串。累加后便是原问题的答案。这个做法
    的时间复杂度为 O（n） .
    SPOJ 694 和SPOJ 705是一样的，就是705的N= 5W,用后缀数组可以轻松搞掉。
    处理完height数组之后，直接利用上述公式，求出所有子串。
    多校第三场的1002我就是用的这个模版，但是T了…
    好吧，不吐槽了。
    //spoj 694
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cmath>
    #include <cstring>
    #include <queue>
    #include <set>
    #include <vector>
    #include <stack>
    #include <map>
    #include <iomanip>
    #define PI acos（-1.0）
    #define Max 2505
    #define inf 1《28
    #define LL（x） （ x 《 1 ）
    #define RR（x） （ x 《 1 | 1 ）
    #define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
    #define ll long long
    #define mem（a,b） memset（a,b,sizeof（a））
    #define mp（a,b） make_pair（a,b）
    #define PII pair<int,int>
    using namespace std;
    /****后缀数组模版****/
    #define N 1005
    #define F（x）（（x）/3+（（x）%3==1 0:tb）） //F（x）求出原字符串的suffix（x）在新的字符串中的起始位置
    #define G（x）（（x）<tb （x）*3+1:（（x）-tb）*3+2） //G（x）是计算新字符串的suffix（x）在原字符串中的位置，和F（x）为互逆运算
    int wa[N],wb[N],wv[N],WS[N];
    int sa[N*3] ;
    int rank1[N],height[N];
    int r[N*3];
    int c0（int *r,int a,int b） {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
    }
    int c12（int k,int *r,int a,int b） {
    if（k==2）
    return r[a]<r[b] || （ r[a]==r[b] && c12（1,r,a+1,b+1） ）；
    else
    return r[a]<r[b] || （ r[a]==r[b] && wv[a+1]<wv[b+1] ）；
    }
    void sort（int *r,int *a,int *b,int n,int m） {
    int i;
    for（i=0; i<n; i++）
    wv[i]=r[a[i]];
    for（i=0; i<m; i++）
    WS[i]=0;
    for（i=0; i<n; i++）
    WS[wv[i]]++;
    for（i=1; i<m; i++）
    WS[i]+=WS[i-1];
    for（i=n-1; i>=0; i--）
    b[--WS[wv[i]]]=a[i];
    return;
    }
    //注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
    void dc3（int *r,int *sa,int n,int m） { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = （n+1）/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for（i=0; i<n; i++） {
    if（i%3!=0）
    wa[tbc++]=i; //tbc表示起始位置模3为1或2的后缀个数
    }
    sort（r+2,wa,wb,tbc,m）；
    sort（r+1,wb,wa,tbc,m）；
    sort（r,wa,wb,tbc,m）；
    for（p=1,rn[F（wb[0]）]=0,i=1; i<tbc; i++）
    rn[F（wb[i]）]=c0（r,wb[i-1],wb[i]）？p-1:p++;
    if（p<tbc）
    dc3（rn,san,tbc,p）；
    else {
    for（i=0; i<tbc; i++）
    san[rn[i]]=i;
    }
    //对所有起始位置模3等于0的后缀排序
    for（i=0; i<tbc; i++） {
    if（san[i]<tb）
    wb[ta++]=san[i]*3;
    }
    if（n%3==1）  //n%3==1,要特殊处理suffix（n-1）
    wb[ta++]=n-1;
    sort（r,wb,wa,ta,m）；
    for（i=0; i<tbc; i++）
    wv[wb[i]=G（san[i]）]=i;
    //合并所有后缀的排序结果，保存在sa数组中
    for（i=0,j=0,p=0; i<ta&&j<tbc; p++）
    sa[p]=c12（wb[j]%3,r,wa[i],wb[j]）？wa[i++]:wb[j++];
    for（； i<ta; p++）
    sa[p]=wa[i++];
    for（； j<tbc; p++）
    sa[p]=wb[j++];
    return;
    }