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!!!! 已改正。
其他细节见代码注释
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月31日 星期日 18时23分53秒
4File Name :code/poj/1743.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=4E4+7;
32const int C=100;
33int n,sa[N],rk[N],t[N],t2[N],cnt[N];
34int height[N];
35int cmp(int *r ,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
36int a[N];
37void getSa( int n,int m)
38{
39 int *x = t;
40 int *y = t2;
41 ms(cnt,0);
42 for ( int i = 0 ; i < n ; i++) cnt[x[i]=a[i]]++;
43 for ( int i = 1 ; i < m ; i++) cnt[i]+=cnt[i-1];
44 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i;
45 for ( int k = 1 ; k <= n ; k<<=1)
46 {
47 int p = 0 ;
48 for ( int i = n-k ; i < n ; i++) y[p++] = i ;
49 for ( int i = 0 ; i < n ; i++) if (sa[i]>=k) y[p++] = sa[i]-k;
50 ms(cnt,0);
51 for ( int i = 0 ; i < n ; i++) cnt[x[y[i]]]++;
52 for ( int i = 0 ; i < m ; i++) cnt[i] +=cnt[i-1];
53 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
54 swap(x,y);
55 p = 1;
56 x[sa[0]] = 0 ;
57 for ( int i = 1 ; i < n; i ++)
58 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
59 if (p>=n) break;
60 m = p;
61 }
62}
63void getHeight( int n)
64{
65 int k = 0;
66 for ( int i = 0 ; i < n; i++) rk[sa[i]] = i ;
67 height[0] = 0 ;
68 for ( int i = 0 ; i < n; i++)
69 {
70 if (rk[i]==0) continue;
71 if (k) k--;
72 int j = sa[rk[i]-1] ;
73 while (a[i+k]==a[j+k]) k++;
74 height[rk[i]] = k;
75 }
76}
77int getSuffix( int s[],int len)
78{
79 int up = 0 ;
80 for ( int i = 0 ; i < len ; i++)
81 {
82 up = max(up,s[i]);
83 }
84 a[len++] = 0;
85 getSa(len,up+1);
86 getHeight(len);
87 return len;
88}
89bool check( int k,int n)
90{
91 int mx,mn;
92 mx=mn=sa[1];
93 // n--;
94 for ( int i = 2 ; i <= n ; i++)
95 {
96 if (height[i]>=k&&i<n)
97 {
98 mn = min(mn,sa[i]);
99 mx = max(mx,sa[i]);
100 continue;
101 }
102 if (mx-mn>=k) return true;
103 mx = mn = sa[i];
104 }
105 return false;
106}
107int main()
108{
109 #ifndef ONLINE_JUDGE
110 freopen("code/in.txt","r",stdin);
111 #endif
112 while (~scanf("%d",&n)&&n)
113 {
114 for ( int i = 0 ; i < n ; i++) scanf("%d",&a[i]);
115 for ( int i = 0 ; i < n-1 ; i++) a[i] = a[i+1]-a[i]+C; //整体平移C=100,防止下标越界。
116 n--; //是因为n个字符只有n-1个变化。
117 n = getSuffix(a,n);// 最后放了一个比所有字符都小的0（1-80+100>0），n比之前多了1
118 // for ( int i = 0 ; i <= n; i++) printf("sa[%d]:%d\n",i,sa[i]);
119 int l = 4,r = n;
120 int ans= 0 ;
121 while (l<=r)
122 {
123 int mid = (l+r)/2;
124 if (check(mid,n))
125 {
126 ans = mid;
127 l = mid+1;
128 }
129 else r = mid-1;
130 }
131 ans++; //最后再增加1是因为，5个字符虽然是4个变化，但是应该算作5个字符。等于是又变了回来。
132 printf("%d\n",ans<5?0:ans);
133 }
134 #ifndef ONLINE_JUDGE
135 fclose(stdin);
136 #endif
137 return 0;gaizheng
138}