本文改编自斯坦福大学CS 97SI: Introduction to Programming Contests的教学材料Suffix arrays – a programming contest approach

在算法竞赛中经常会遇到很多有关字符串子串的问题,或者是字符串后缀的问题,因此也就需要一种高效的数据结构及算法来处理这个问题。

什么是后缀数组?

为了更好地理解后缀数组,我们先来了解一种特殊的trie——后缀trie。一棵trie树是用来储存字符串的数据结构,其中每一个节点有和字母表大小一样多的孩子节点。本文的例子中只考虑小写字母,那么每个节点也就至多有26个孩子节点。每一条从父节点到孩子节点标注上一个字符,从根节点到叶子节点路径上标注的字符组合起来就是trie中保存着的一个字符串。显然地,在trie中查找一个字符串只需要时间复杂度(m是字符串长度),叟搜索时间和其中的字符串数量无关,这是一个实现字典的绝佳数据结构。

后缀trie就是把字符串的所有后缀保存到一个trie中,例如字符串”abc”的trie数如下:

c
c
b
b
a
a
1
1
a
a
7
7
c
c
b
b
2
2
10
10
c
c
4
4
6
6
a
a
3
3
9
9
c
c
8
8
5
5

一些常见的操作可以这样完成:

  • 检查字符串w是不是字符串a的子串:只需要从根节点开始,查找是否存在一条路径和字符串W对应(时间复杂度
  • 寻找字符串两个后缀的最长公共前缀:既然后缀对应trie中的两个节点,那么最长公共前缀也就是要求两个节点的最近公共祖先。例如,”abac”和”ac”分别对应节点5和6,它们的最近公共祖先是节点2。
  • 找到所有后缀中字典序为k的后缀:(时间复杂度,主要花费在预处理上)例如,”abac”的第3个后缀就是第三个叶子节点。

上面的操作的效率看起来可以接受,但是后缀trie的构建过程时间复杂度为,所以还是试试别的数据结构了。

让我们仔细研究一下深度优先遍历后得到字符串a的后缀,排列符合字典序:

保存它们并不需要把每个后缀字符串都保存起来,只需要记录每个后缀在原字符串的开始位置就好了,上面的后缀数组可以保存成

如何创建后缀数组?

首先,排序过程的时间复杂度为,比较两个后缀的时间复杂度为,因此最终对后缀排序的时间复杂度为,不是非常高效,不如试试其他方法。

本文介绍倍增法,倍增法每次只对所有后缀按照长度为的前缀进行排序,所以总共只需要排序次。算法需要一个m×n大小的矩阵P来保存中间结果,用表示字符串a从i开始长度为子串,数组中顺序保存在中。

每次从第k步到第k+1步时,所有形如的子串将被合并,于是子串长度过渡到。为了求出新的排序,上一步的顺序要利用起来。对于每一个下标i,都创建一个序对。当然,可能会超出矩阵P的范围,那样的话使用一个小于任何字符的$替代。对这些序对进行排序之后,也就得到了长度为子串的顺序。还有个需要注意的地方就是如果在某一步中有,那么需要设置相同值。

“bobocel”的后缀数组的创建过程如下:

第0步:

0404123
bobocel

第1步:

0405123
bobocel
obocel$

第2步:

0516234
bobocel
obecel$
bocel$$
ocel$$$

第3步:

0516234
bobocel
obocel$
bocel$$
ocel$$$
cel$$$$
el$$$$$
l$$$$$$
$$$$$$$

现在算法的时间复杂度取决于排序算法了,如果使用基数排序的话,那么最终时间复杂度为。如果使用STL中的sort话,代码实现会简单很多,时间复杂度为,如果字符串长度小于100,000的话,两种方法并没有明显的性能差异。

#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std;  
#define MAXN  65536 
#define MAXLG 17  
char A[MAXN]; 
struct entry {     
  int nr[2], p; 
} L[MAXN]; 
int P[MAXLG][MAXN], N, i, stp, cnt;  
int cmp(struct entry a, struct entry b) 
{     
  return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0); 
}  
int main(void) {     
  gets(A);    
  for (N = strlen(A), i = 0; i < N; i ++)         
    P[0][i] = A[i] - 'a';     
  for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1) {         
    for (i = 0; i < N; i ++) {             
      L[i].nr[0] = P[stp - 1][i];             
      L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;            
      L[i].p = i;         
    }         
    sort(L, L + N, cmp);         
    for (i = 0; i < N; i ++)            
      P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;     
  }     
  return 0; 
} 

矩阵P中最后一行就是后缀数组了。如果中间过程不再需要的话,矩阵其实可以缩减为两行交替使用。

如何计算最长公共前缀?

直接计算

对于两个后缀,我们可以根据矩阵P的值,从最大的k到0来检查。如果相等,只需要给i和j增加,继续检查前缀。

int lcp(int x, int y) {     
  int k, ret = 0;     
  if (x == y) return N - x;     
  for (k = stp - 1; k >= 0 && x < N && y < N; k --)         
    if (P[k][x] == P[k][y])             
      x += 1 << k, y += 1 << k, ret += 1 << k;     
  return ret; 
}

这个算法时间复杂度为,如果查询次数比较多的话,还是考虑一下的算法吧。

$height$数组

首先定义在后缀数组中的序号为,定义后缀数组中第i个后缀的开始位置(也就是下标)为。然后,我们定义,也就是后缀数组中每个后缀与前一个后缀的最长公共前缀。之所以需要这个数组是因为它可以在线性时间内被求解出来。

数组性质

证明

  • 显然成立
  • ,设j-1为后缀数组中前面一个后缀(),的首字符c是相同的。根据后缀下标的定义,,所以,并且保持。由于后缀数组是有序的,因此次序位于中的后缀必须满足,证明完毕。
for (int i = 0; i < n; i++) {
    rank[i] = p[step-1][i];
    sa[rank[i]] = i;
}
for (int i = 0, j = 0; i < n; i++) {
    if (j) j--;
    while (rank[i] && str[i+j] == str[sa[rank[i]-1]+j]) j++;
    height[rank[i]] = j;
}

常数算法

得到数组之后,,LCP问题变成了RMQ问题,使用ST算法即可在时间内完成一次查询(需要的预处理时间)。

预处理
for (int i = 0; i < n; i++)
    st[i][0] = height[i];
for (int j = 1, step = 1; step < n; j++, step <<= 1)
    for (int i = 0; i < n; i++)
        if (i + step < n)
            st[i][j] = MIN(st[i][j-1], st[i+step][j-1]);
        else
            st[i][j] = st[i][j-1];
查询
int lcp(int a, int b)
{
	if (a == b)
		return n - a;
	int i = MIN(rank[a], rank[b]) + 1;
	int j = MAX(rank[a], rank[b]);
	int seg = log2(j-i+1);
	return MIN(st[i][seg], st[j-(1<<seg)+1][seg]);
}

后缀数组本身不难,分析问题,借助后缀数组解决才是难点