后缀数组

发表于 | 分类于

简介

后缀数组可以解决一些有限制条件的字串问题，程序短小，但较为抽象，需要一定时间阅读代码理解。结合论文可以更好地理解后缀数组，论文下载链接附在上面。

1 后缀数组的实现

1.1定义

1.子串(substring)：字符串$S$的子串$r[i…j]$ $(0<i≤j<len(s))$即为$r[i],r[i+1],r[i+2]…r[j]$所构成的字符串。

2.后缀(suffix)：从某个位置$i$开始的到字符串尾的子串，即$r[i…len(s)]$。

3.大小：对于c++ stl库里的string自带了比较功能，但由于速度较慢，一般在算法竞赛中不常用，多用字符数组来代替。由字典序来比较字符串大小。

4.后缀数组：后缀数组在论文中用$sa[]$命名，在此延续此定义。$sa[i]$表示的是对字符串进行基数排序后，排名第$i$的字符串在原字符串中的位置。

5.排名数组：排名数组论文中用$rank[]$命名，是后缀数组的反函数，即$rank[]=sa[]^{-1}$，易得$rank[sa[i]]=i$，故求得$sa[]$后可以一层循环求出$rank[]$。

6.基数排序：在后缀数组的计算中，论文中主要讲到了$O(n)$的基数排序，也可以使用$O(n*log(n))$的快速排序，由于时间复杂度比较低，在此不做讲解。

1.2倍增算法的实现

倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为$2^k$的子字
符串进行排序，求出排名，即$rank$值。$k$从$0$开始，每次加$1$，当$2^k$大于$n$以
后，每个字符开始的长度为$2^k$的子字符串便相当于所有的后缀。并且这些子字
符串都一定已经比较出大小，即$rank$值中没有相同的值，那么此时的$rank$值就
是最后的结果。每一次排序都利用上次长度为$2^{k-1}$的字符串的$rank$值，那么长
度为$2^k$的字符串就可以用两个长度为$2^{k-1}$ 的字符串的排名作为关键字表示，然
后进行基数排序，便得出了长度为$2^k$的字符串的$rank$值。以字符串 $“aabaaaab ”$
为例，整个过程如图所示。其中$x$、$y$是表示长度为$2^k$的字符串的两个关键字 。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    memset(tong,0,sizeof(tong));
    for(i=0;i<n;i++) 
        tong[x[i]=r[i]]++;
    for(i=1;i<m;i++) 
        tong[i]+=tong[i-1];
    for(i=n-1;i>=0;i--) 
        sa[--tong[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]];
        memset(tong,0,sizeof(tong));
        for(i=0;i<n;i++) 
            tong[wv[i]]++;
        for(i=1;i<m;i++) 
            tong[i]+=tong[i-1];
        for(i=n-1;i>=0;i--) 
            sa[--tong[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++;
    }
}

TIPS

1.后缀数组$sa[]$本代码求出的是从$0$开始的，看清题目要求，再做。

2.$da()$函数调用时要传递进去$len(s)+1$，具体原因请读者自行思考。

3.代码逐行解释参考论文。

2.后缀数组的应用

2.1 最长公共前缀

attention！

以下内容十分重要，需要认真阅读，这对题目的分析有很大帮助

1.定义$height[]$数组，其中$height[i]$为$suffix(sa[i-1])$和$suffix(sa[i])$的最长公共前缀，即排名相邻的两个后缀的最长公共前缀。那么对于$j$和$k$，不妨设$rank[j]<rank[k]$,则有以下性质：

$suffix(j)$和$suffix(k)$的最长公共前缀为$height[rank[j]+1],height[rank[j]+2],$ $height[rank[j]+3],…,height[rank[k]]$中的最小值。

例如，字符串为$“aabaaaab”$，求后缀$“abaaaab”$和后缀$“aaab”$的最长公共前缀，如图所示：

如果按$height[2]，height[3]，……，height[n]$的顺序计算，最坏情况下时间复杂度为$O(n^2)$。这样做并没有利用字符串的性质。定义$h[i]=height[rank[i]]$，也就是 suffix(i)和在它前一名的后缀的最长公共前缀。

$h[]$数组有以下性质：

$h[i] ≥ h[i-1]-1$

证明：

设$suffix(k)$是排在$suffix(i-1)$前一名的后缀，则它们的最长公共前缀是$h[i-1]$。那么$suffix(k+1)$将排在$suffix(i)$的前面（这里要求$h[i-1]>1$，如果$h[i-1]≤1$，原式显然成立）并且$suffix(k+1)$和$suffix(i)$的最长公共前缀是$h[i-1]-1$，所以$suffix(i)$和在它前一名的后缀的最长公共前缀至少是$h[i-1]-1$。按照$h[1],h[2],…,h[n]$的顺序计算,并利用$h[]$数组的性质，时间复杂度可以降为$O(n)$。

code

1
2
3
4
5
6
7
8
void calheight(char *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++);
}

模板题(sa与height计算) UOJ35

3.论文例题

例1

最长公共前缀

给定某个字符串，询问某两个后缀的最长公共前缀。

按照上面所说的做法，求两个后缀的最长公共前缀可以转化为求某个区间上的最小值。对于这个RMQ问题（如果对RMQ问题不熟悉，请阅读其他相关资料），可以用$O(nlog(n))$的时间先预处理，以后每次回答询问的时间为$O(1)$。所以对于本问题，预处理时间为$O(nlog(n))$,次回答询问的时间为$O(1)$ 。如果RMQ问题用$O(nlog(n))$ 的时间预处理，那么本问题的时间复杂度可以做到$O(nlog(n))$ 。

定义：

重复子串：字符串$R$在字符串$L$中至少出现两次，则称$R$是$L$的重复子串

例2

可重叠最长重复子串

给定一个字符串，求最长重复子串，这两个子串可以重叠。

这道题是后缀数组的一个简单应用。做法比较简单，只需要求$height[]$数组里的最大值即可。首先求最长重复子串，等价于求两个后缀的最长公共前缀的最大值。因为任意两个后缀的最长公共前缀都是$height[]$数组里某一段的最小值，那么这个值一定不大于$height$数组里的最大值。所以最长重复子串的长度就是$height[]$数组里的最大值。这个做法的时间复杂度为$O(n)$。

例3 不可重叠最长重复子串

Musical Theme

POJ1743

Time Limit: 1000MS         
Memory Limit: 30000K 
Total Submissions: 28244        
Accepted: 9543

Description

A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings.
Many composers structure their music around a repeating &qout;theme&qout;, which, being a subsequence of an entire melody, is a sequence of integers in our representation. A subsequence of a melody is a theme if it:
is at least five notes long
appears (potentially transposed – see below) again somewhere else in the piece of music
is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)

Transposed means that a constant positive or negative value is added to every note value in the theme subsequence.
Given a melody, compute the length (number of notes) of the longest theme.
One second time limit for this problem’s solutions!
Input

The input contains several test cases. The first line of each test case contains the integer N. The following n integers represent the sequence of notes.
The last test case is followed by one zero.

Output

For each test case, the output file should contain a single line with a single integer that represents the length of the longest theme. If there are no themes, output 0.

Sample Input

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
0

Sample Output

5

Hint

Use scanf instead of cin to reduce the read time.

Source

LouTiancheng@POJ