POJ 1743 Musical Theme(后缀数组，最长重复子串)

/*
题意：用数字代表音节，寻找最长主旋律，要求：不少于五个数字，不能重复；并不要求两段子串完全相同，相加同一个数字后相同也可以

题解：我原来把字符串相加一个数字后做了一次拼接，结果超时。其实这道题，更好的解法是，另建一个数组存储前后数据之差，这样如果，
存在主旋律，则这段字符串必然相等。然后问题就可以解决了。不过需要注意，最后结果需要加1

这道题做了很久，最后AC，收获很大，①到④是曾经出现过的错误。这道题的数据有些弱，需要自己做好判断
*/

#include <iostream>
using namespace std;
const int nMax = 20010;
//const int mMax = 180;
int wa[nMax], wb[nMax];
int wz[nMax], wv[nMax];//①，wz[]下标最后会转变为排名，所以也需要定义为nMax
int sa[nMax], rank[nMax], height[nMax];
int N;
int A[nMax], AA[nMax];

int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<m;i++) wz[i]=0;
	for(i=0;i<n;i++) wz[x[i]=r[i]]++;
	for(i=1;i<m;i++) wz[i]+=wz[i-1];
	for(i=n-1;i>=0;i--) sa[--wz[x[i]]]=i;
	for(j=1,p=1;p<n;j*=2,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<n;i++) wv[i]=x[y[i]];
		for(i=0;i<m;i++) wz[i]=0;
		for(i=0;i<n;i++) wz[wv[i]]++;
		for(i=1;i<m;i++) wz[i]+=wz[i-1];
		for(i=n-1;i>=0;i--) sa[--wz[wv[i]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
	return;
}

//int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)//height[]的有效范围[2,N - 1],因为height[1]永远是0，总共有N - 1个元素
		for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);//以前这里也是有错误，但是为什么呢？因为原来你的AA[N-1]中没有存数据
		return;
}

int bsearch(int left, int right, int n)
{
	int l = left,
		r = right;
	int max, min;
	while(l + 1 < r)
	{
		int mid = (l + r) / 2;
		//int max = 0, min = 90;
		int i;
		bool flag = 0;
		max = min = sa[1];//②，需要搞清楚这里的处理关系
		for(i = 2; i <= n; ++ i)//③，需要等于n，因为height[]的有效范围是[2,N - 1];
		{
			if(height[i] < mid)
			{
				if(max - min > mid)//这里需要推断一下
				{
					flag = 1;
					break;
				}
				max = min = sa[i];//②
			}
			else
			{
				if(sa[i] > max) max = sa[i];
				if(sa[i] < min) min = sa[i];
			}
		}
		if(max - min > mid)
			flag = 1;
		if(flag == 1) l = mid;
		else r = mid;
	}
	return l + 1;
}

int main()
{
	//freopen("e://data.in", "r", stdin);
	while(scanf("%d", &N) != EOF && N)
	{
		int i;
		for(i = 0; i < N; ++ i) 
		{
			scanf("%d", &A[i]);
			if(i)
				AA[i - 1] = A[i] - A[i - 1] + 88;
		}
		AA[N - 1] = 0;
		da(AA, sa, N, 180);//④，这里的m只需要最大元素即可
		calheight(AA, sa, N - 1);
		int ans = bsearch(0, N - 1, N - 1);//最小值为0
		if(ans >= 5)
			printf("%d\n", ans);
		else
			printf("0\n");
	}
	return 0;
}