题目链接：http://poj.org/problem?id=1743
题目大意：给定一个序列，可从中选择一个子段，可以对这个子段各个数进行增加k或者减少k的操作，问满足子段长度大于5并且两个子段不重叠的最长的重复子段长度是多少？
解题思路：本题可用后缀数组解决。看到这题目就能想到后缀树组，因为是重复子段问题，由此观之后缀数组不仅仅解决字符串问题，其它重复子段问题也都ok，KMP也是如此。由于每个子段可进行增加k或者减少k操作，那么判断x1,y1和x2,y2能够匹配（匹配了才会重复）只要x1-y1 == x2-y2，所以将初始的长度为n的序列转化为长度为n-1的差值序列。
预处理完，便可开始求sa数组、rank数组、height数组，这些都可以套模板，自己敲也行，像我就自己敲了，但是果断错了。处理完之后，理想状态是只要找height数组中最大的值就ok了，但理想是丰满的，现实是骨感的。因为两个子段不能重叠，所以不能这样做。举个例子，22222222，9个2，如果找最大的height数组，答案是8，提交华丽丽地就Wa了。问题转化为寻找符合不重叠条件的长度大于5的最大长度，这是判定性问题，可以用二分查找从0---n/2内找最优解。每次算出mid
= （maxx + minn) / 2，再将height小于mid的后缀排除，留下height大等于mid的一陀后缀，只要找其中最大的差值并判断是否大于mid即可。为什么这样判断就行呢，先想想，height小于mid的情况是它和其它各后缀的最长公共前缀长度小于mid，这不符合条件。而另外一坨height都大于mid，能否符合条件就很清楚了。
测试数据：
Input:
9
2 2 2 2 2 2 2 2 2
11
2 2 2 2 2 2 2 2 2 2 2
13
2 2 2 2 2 2 2 2 2 2 2 2 2
30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80
OutPut:
0
6
7
5
代码：
#include <stdio.h>
#include <string.h>
#define MAX 100000
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
int n,arr[MAX];
int wa[MAX],wb[MAX];
int wv[MAX],wn[MAX];
int sa[MAX],rank[MAX],h[MAX];
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 n,int m) {
int i,j,k,p; //p 不同字符串个数
int *x = wa,*y = wb,*t;//rank值保存在x中
//对r中长度为1的子串进行基数排序
for (i = 0; i < m; ++i) wn[i] = 0;
for (i = 0; i < n; ++i) wn[x[i]=r[i]]++;
for (i = 1; i < m; ++i) wn[i] += wn[i-1];
for (i = n - 1; i >= 0; --i) sa[--wn[x[i]]] = i;
//对r中长度为j的子串进行基数排序
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) wn[i] = 0;
for (i = 0; i < n; ++i) wn[wv[i]]++;
for (i = 1; i < m; ++i) wn[i] += wn[i-1];
for (i = n - 1; i >= 0; --i) sa[--wn[wv[i]]] = y[i];
t = x,x = y,y = t,p = 1;
for (x[sa[0]] = 0,i = 1; i < n; ++i)
x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p - 1: p++;
}
}
void Calheight(int *r,int n) {
int i,j,k = 0;
for (i = 1; i <= n; ++i) rank[sa[i]] = i; //sa转化为rank
for (i = 0; i < n; h[rank[i++]] = k)
for (k ? k--:0,j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
}
int Solve(int n) {
int i,j,k,ans = 0,flag;
int minn,maxx,low,high,mid;//mid,minn和maxx指长度，low和high指sa的值
minn = 0,maxx = n / 2;
while (minn <= maxx) {
mid = minn + (maxx - minn) / 2;
flag = 0,low = high = sa[1];
for (i = 2; i <= n && !flag; ++i) {
if (h[i] < mid) low = high = sa[i];
else {
low = min(low,sa[i]);
high = max(high,sa[i]);
if (high - low >= mid) flag = 1;
}
}
if (flag) minn = mid + 1;
else maxx = mid - 1;
}
return maxx >= 4 ? maxx + 1 : 0;
}
int main()
{
int i,j,k,ans;
while (scanf("%d",&n),n) {
for (i = 0; i < n; ++i)
scanf("%d",&arr[i]);
for (i = 0; i < n - 1; ++i)
arr[i] = (arr[i] - arr[i+1]) + 100;
arr[n-1] = 0;
Da(arr,n,200);
Calheight(arr,n-1);
ans = Solve(n-1);
if (n < 10) printf("0\n");
else printf("%d\n",ans);
}
}
本文ZeroClock原创，但可以转载，因为我们是兄弟。