poj 1743 Musical Theme (不可重叠最长重复子串，后缀数组)
题意：n个数字（1..88）表示的音符，问最长的连续两段长度至少为5的变化相同的音符段的长度。。。
思路：求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。
先二分答案,把题目变成判定性问题:判断是否 存在两个长度为 k 的子串是相同的,且不重叠。解决这个问题的关键还是利用 height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的 height 值都 不小于 k。例如,字符串为“aabaaaab”,当 k=2 时,后缀分成了 4 组,如图 5 所示。
容易看出,有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然 后对于每组后缀,只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于 k。如果有一组满足,则说明存在,否则不存在。整个做法的时间复杂度为 O(nlogn)。**本题中利用 height 值对后缀进行分组的方法很常用,**请读者认真体 会。
这是论文中的题目。这个做法的确想不到，不过很好理解。
如果没有不允许重叠的条件就变成了求所有height[i]中的最大值，而每个height[i]对应的两个后缀的位置是sa[i]和sa[i-1]。
分组使得每组中的height[i]都大于等于k(那height[i]小于k的去哪里了？ 因为height[i]是由两个相邻的后缀得到的，如果某两个后缀的height[i]小于k,只需要将这两个后缀分成两组，这样这个height[i]就不存在了，从而保证了每组中的height[i]都大于等于k)
而我们知道，任意两个后缀的最长公共前缀是他们之间的所有height的最小值。因为对于处于同一组内的两个后缀来说，由于之前保证了每组中的height[i]>=k,也就是保证了任意两个后缀的最长公共前缀大于等于k.
因此用二分判定长度k的时候，这样分组以后，只需要再判断是否相交（也就是如果长度k不满足，可能是因为没有办法分组使得每个height都大于等于k,也可能是存在这样的分组，但是两个后缀相交）。
判断相交其实非常简单，sa[i]表示的是排名第i的后缀的开始位置，那么如果存在sa[j]-sa[i]>=k（其实是sa[i]+k-1<sa[j],sa[i]位置开始的后缀的长度为k的前缀的最后一个字符的所在位置sa[i]+k-1比sa[j]小，就说明不相交，由于是整数，就可以变成sa[i]+k<=sa[j]，也就是sa[j]-sa[i]>-=k）
而某一组内只要有一组i,j，满足sa[j]-sa[i]>=k就是有解，因此我们只需要判断最可能符合条件的一组，也就是找到一组中sa[i]的最大值和最小值，也正因为我们这样，我们在具体实现的过程中也没必要真的模拟分组的过程，只需要一直更新两个极值即可。
以及：lrj的板子是错的！！会re!!!! 已改正。
其他细节见代码注释
/* ***********************************************
Author :111qqz
Created Time :2016年07月31日 星期日 18时23分53秒
File Name :code/poj/1743.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=4E4+7;
const int C=100;
int n,sa[N],rk[N],t[N],t2[N],cnt[N];
int height[N];
int cmp(int *r ,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
int a[N];
void getSa( int n,int m)
{
int *x = t;
int *y = t2;
ms(cnt,0);
for ( int i = 0 ; i < n ; i++) cnt[x[i]=a[i]]++;
for ( int i = 1 ; i < m ; i++) cnt[i]+=cnt[i-1];
for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i;
for ( int k = 1 ; k <= n ; k<<=1)
{
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;
ms(cnt,0);
for ( int i = 0 ; i < n ; i++) cnt[x[y[i]]]++;
for ( int i = 0 ; i < m ; i++) cnt[i] +=cnt[i-1];
for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
swap(x,y);
p = 1;
x[sa[0]] = 0 ;
for ( int i = 1 ; i < n; i ++)
x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
if (p>=n) break;
m = p;
}
}
void getHeight( int n)
{
int k = 0;
for ( int i = 0 ; i < n; i++) rk[sa[i]] = i ;
height[0] = 0 ;
for ( int i = 0 ; i < n; i++)
{
if (rk[i]==0) continue;
if (k) k--;
int j = sa[rk[i]-1] ;
while (a[i+k]==a[j+k]) k++;
height[rk[i]] = k;
}
}
int getSuffix( int s[],int len)
{
int up = 0 ;
for ( int i = 0 ; i < len ; i++)
{
up = max(up,s[i]);
}
a[len++] = 0;
getSa(len,up+1);
getHeight(len);
return len;
}
bool check( int k,int n)
{
int mx,mn;
mx=mn=sa[1];
// n--;
for ( int i = 2 ; i <= n ; i++)
{
if (height[i]>=k&&i<n)
{
mn = min(mn,sa[i]);
mx = max(mx,sa[i]);
continue;
}
if (mx-mn>=k) return true;
mx = mn = sa[i];
}
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
while (~scanf("%d",&n)&&n)
{
for ( int i = 0 ; i < n ; i++) scanf("%d",&a[i]);
for ( int i = 0 ; i < n-1 ; i++) a[i] = a[i+1]-a[i]+C; //整体平移C=100,防止下标越界。
n--; //是因为n个字符只有n-1个变化。
n = getSuffix(a,n);// 最后放了一个比所有字符都小的0（1-80+100>0），n比之前多了1
// for ( int i = 0 ; i <= n; i++) printf("sa[%d]:%d\n",i,sa[i]);
int l = 4,r = n;
int ans= 0 ;
while (l<=r)
{
int mid = (l+r)/2;
if (check(mid,n))
{
ans = mid;
l = mid+1;
}
else r = mid-1;
}
ans++; //最后再增加1是因为，5个字符虽然是4个变化，但是应该算作5个字符。等于是又变了回来。
printf("%d\n",ans<5?0:ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;gaizheng
}