子串: 字符串s的子串r[i..j],i<=j,表示r串中從 i 到 j 這一段。

后綴: 后綴是從某個位置 i 開始到整個串末尾結束的一個特殊子串。

        也就是說suffix(i)=r[i..len(s)];

后綴數組：后綴數組sa是一個一維數組，它保存的是1..n的某個排列.

　　　　　sa[1],sa[2],..,sa[n],并保證suffix(sa[i]) < suffix(sa[i+1])

              也就是將s的n個后綴從小到在進行排序之后把排好序的后綴

              的開頭位置順序放入sa中。

名次數組：名次數組rank[i]保存的是suffix(i)在所有后綴中從小到大排列的名次。

后綴數組是排列第幾是誰。

名次數組是你排第幾。

如果還是不清楚，就看看我個人的所思所得吧，絕對原創。

名次                          1      2      3       4       5       6       7      8
排序后的后綴su順序為 su[4] su[5] su[6] su[1] su[7] su[2] su[8] su[3]
                            aaaab aaab   aab   ……
                              ||
                              \/
                   第4個后綴排在第一位
故：
排序后的名次ra順序為 ra[4] ra[5] ra[6] ra[1] ra[7] ra[2] ra[8] ra[3]
                             ||     ||     ||     ||    ||     ||    ||     ||
                             1      2       3      4     5     6     7    8

故：
后綴數組sa為：       sa[1] sa[2] sa[3] sa[4] sa[5] sa[6] sa[7] sa[8]
                             ||     ||     ||     ||    ||     ||     ||    ||
                             4      5      6      1     7     2      8     3

很明顯的看到：ra[x]=y; sa[y]=x; 相反啊！

常用的數組組合：

su[sa[i]]就表示排序為第 i 的后綴，也就是說su[sa[1]]就是排在第一的后綴。

用倍增的方法求rank[i]的具體過程為：

View Code

待排序的字符串放在r 數組中，從r[0]到r[n-1]，長度為n，且最大值小于m。

為了函數操作的方便，約定除r[n-1]外所有的r[i]都大于0, r[n-1]=0。
函數結束后，結果放在sa 數組中，從sa[0]到sa[n-1]。

下面介紹一個非常有用的數組height[]數組：

height[i]=su[sa[i-1]] 和 su[sa[i]]的最長公共前綴。

                      aaaab…………………… su[1]

height[2]=3      aaab………………………su[2]    

height[3]=2      aab…………………………su[3]

height[4]=3      aabaaaab……………… su[4]

height[5]=1      ab……………………………su[5]

height[6]=2      abaaaab………………… su[6]

height[7]=0      b………………………………su[7]

height[8]=1      baaaab……………………su[8]

這個height[]數組有什么用呢？

對于su[j]和su[k]，不妨設rank[j]<rank[k],（這個不妨是個重點）

那么su[j]和su[k]的最長公共前綴為

min(height[ra[j]+1], height[ra[j]+2]……height[ra[k]]);

所以，su[1]和su[5]的最長公共前綴為

可以看到ra[1]=5 ra[5]=2；

min(height[2+1],height[2+2], height[2+3]) = min(2, 3, 1) = 1;      

再來看一個例子吧。

su[2]和su[6]的最長公共前綴為

可以看到ra[2]=6 ra[6]=3  

min(height[3+1], height[3+2], height[3+3])=min(3, 1, 2)=1;

用o(n)的方法計算出height[n]的代碼如下： 

View Code

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)
    for(k?k--;0, j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}