前两天在yjw神牛和hyf神牛的共同努力下终于学会了后缀数组O(nlogn)倍增构造方法。
构造：
定义s[k][i]表示从s字符串的第i位开始的长度为k的一个字符串(后缀)，不够的补零，sa[k][i]表示在所有长度为k的后缀中排序后大小为第i的后缀的位置。显然sa[1]可以直接qsort得到。当sa[k]求到过后，sa[2k]的每个元素都可以O(1)比较得出，这时用桶排，把sa[k]中排名相同的放在一起（放在一个桶里），那么对于每个不同的桶中的元素，他们之间的大小关系就已经确定了，对于同一个桶中的元素，s[2k][i]的前k位是一样的，可能不一样只有后k位，而这个我们是已经得到了的，所以通过sa[k][i]可以算出sa[2k][i-k]，桶排把排序过程复杂度降成了O(n)，总体构造的复杂度就成了O(nlogn)。DC3算法貌似可以把复杂度降到O(n)...暂时只有膜拜的份了。
现在定义sa[i]为所有后缀排好序后的第i个后缀在原序列中的位置。
定义rank[i]为后缀s[i]在后缀排好序的序列中的排名。
当sa数组求出来了过后，就可以构造h和height数组了。
定义height数组为排好序的后缀中相邻两项的LCP(最常公共前缀)，即height[i] = LCP(sa[i],sa[i-1])。
定义h数组为原序列中的某个后缀与排好序的后缀中它的前一个的LCP，即h[i] = LCP(i,sa[rank[i]-1])。
然后有一个hyf和yjw神牛都不知道怎么来的很牛X的定理：h[i]>=h[i-1]-1。。。所以就可以在O(n)时间内直接for出这个h数组来。。。（这步是最诡异也最精髓的，因为没有这个数组后缀数组就没什么用了。。求神牛们讲解下这个定理的证明。。）
求出了h数组后height数组也可以直接得到。
实现方式是用了两个指针轮番上阵，看起来可能会有点纠结。。
应用：
有了h和height数组后，我们就可以用它来做很多事情。但我还不是很熟，只会求一个字符串里面可以相交的最长重复字串的长度。。
cii(uva?)3901 Editor就是这样一道题。
比如abcabcabc的最长重复字串就是abcabc。
其实求出了h和height数组后就变得很简单，就是h或height数组中最大的一个。
欢迎大牛神牛们前来补充和指正！
1 /*
2 * $Date: Fri Nov 27 09:00:37 2009 CST
3 * $File: 3901.cpp
4 */
5 #include <iostream>
6 #include <cstdio>
7 #include <cstdlib>
8 #include <cstring>
9 #include <algorithm>
10 #define MAXLEN 50000
11
12 using namespace std;
13
14 char s[MAXLEN+1];
15 bool cmp(const int &a,const int &b){
16 return s[a]<s[b];
17 }
18
19 int sa[MAXLEN+1],rank[MAXLEN+1],tmp1[MAXLEN+1],tmp2[MAXLEN+1];
20 int h[MAXLEN+1],height[MAXLEN+1];
21
22 void Solve(){
23 scanf("%s",s);
24 int n = strlen(s);
25 s[n++] = 0;
26 for (int i = 0; i<n; i++)
27 sa[i] = i;
28 sort(sa,sa+n,cmp);
29
30 rank[sa[0]] = 0;
31 for (int i = 1; i<n; i++)
32 if (s[sa[i]]==s[sa[i-1]])
33 rank[sa[i]] = rank[sa[i-1]];
34 else
35 rank[sa[i]] = rank[sa[i-1]]+1;
36
37 int *s1 = sa,*s2 = tmp1,*b = tmp2, *r = rank;
38 for (int i = 1; i<n&&r[sa[n-1]]<n-1; i<<=1){
39 //b is the barrel
40 for (int j = 0; j<n; j++)
41 b[r[s1[j]]] = j;
42 for (int j = n-1; j>=0; j--)
43 if (s1[j]>=i)
44 s2[b[r[s1[j]-i]]--] = s1[j]-i;
45 for (int j = n-i; j<n; j++)
46 s2[b[r[j]]] = j;
47 swap(s1,s2);
48 b[s1[0]] = 0;//cause the barrel is now useless, use b as the new rank array
49 for (int j = 1; j<n; j++)
50 if (r[s1[j]]!=r[s1[j-1]]||r[s1[j]+i]!=r[s1[j-1]+i])
51 b[s1[j]] = b[s1[j-1]]+1;
52 else
53 b[s1[j]] = b[s1[j-1]];
54 swap(b,r);
55 }
56 //calc
57 for (int i = 0; i<n; i++){
58 if (r[i] == 0)
59 h[i] = 0;
60 else if (i == 0||h[i-1] == 0)
61 for (h[i] = 0; s[i+h[i]]==s[s1[r[i]-1]+h[i]];h[i]++);
62 else
63 for (h[i]=h[i-1]-1 ; s[i+h[i]]==s[s1[r[i]-1]+h[i]];h[i]++);
64 }
65 int Ans = 1;
66 for (int i = 0; i<n; i++)
67 Ans = max(Ans,h[i]);
68 printf("%d\n",Ans);
69 }
70 int main(){
71 int t;
72 scanf("%d",&t);
73 while (t--)
74 Solve();
75 return 0;
76 }
77