前兩天在yjw神牛和hyf神牛的共同努力下終于學(xué)會了后綴數(shù)組O(nlogn)倍增構(gòu)造方法。
構(gòu)造：
定義s[k][i]表示從s字符串的第i位開始的長度為k的一個字符串(后綴)，不夠的補(bǔ)零，sa[k][i]表示在所有長度為k的后綴中排序后大小為第i的后綴的位置。顯然sa[1]可以直接qsort得到。當(dāng)sa[k]求到過后，sa[2k]的每個元素都可以O(shè)(1)比較得出，這時用桶排，把sa[k]中排名相同的放在一起（放在一個桶里），那么對于每個不同的桶中的元素，他們之間的大小關(guān)系就已經(jīng)確定了，對于同一個桶中的元素，s[2k][i]的前k位是一樣的，可能不一樣只有后k位，而這個我們是已經(jīng)得到了的，所以通過sa[k][i]可以算出sa[2k][i-k]，桶排把排序過程復(fù)雜度降成了O(n)，總體構(gòu)造的復(fù)雜度就成了O(nlogn)。DC3算法貌似可以把復(fù)雜度降到O(n)...暫時只有膜拜的份了。
現(xiàn)在定義sa[i]為所有后綴排好序后的第i個后綴在原序列中的位置。
定義rank[i]為后綴s[i]在后綴排好序的序列中的排名。
當(dāng)sa數(shù)組求出來了過后，就可以構(gòu)造h和height數(shù)組了。
定義height數(shù)組為排好序的后綴中相鄰兩項的LCP(最常公共前綴)，即height[i] = LCP(sa[i],sa[i-1])。
定義h數(shù)組為原序列中的某個后綴與排好序的后綴中它的前一個的LCP，即h[i] = LCP(i,sa[rank[i]-1])。
然后有一個hyf和yjw神牛都不知道怎么來的很牛X的定理：h[i]>=h[i-1]-1。。。所以就可以在O(n)時間內(nèi)直接for出這個h數(shù)組來。。。（這步是最詭異也最精髓的，因為沒有這個數(shù)組后綴數(shù)組就沒什么用了。。求神牛們講解下這個定理的證明。。）
求出了h數(shù)組后height數(shù)組也可以直接得到。
實現(xiàn)方式是用了兩個指針輪番上陣，看起來可能會有點糾結(jié)。。
應(yīng)用：
有了h和height數(shù)組后，我們就可以用它來做很多事情。但我還不是很熟，只會求一個字符串里面可以相交的最長重復(fù)字串的長度。。
cii(uva?)3901 Editor就是這樣一道題。
比如abcabcabc的最長重復(fù)字串就是abcabc。
其實求出了h和height數(shù)組后就變得很簡單，就是h或height數(shù)組中最大的一個。
歡迎大牛神牛們前來補(bǔ)充和指正！
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