后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能，而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。

概念

  • 后缀：设一个字符串为S[0 ~ |S|-1]，后缀i表示S[i ~ |S|-1]。举例：有一个字符串BANANA，后缀3就是ANA。
  • 后缀数组：后缀数组sa保存的是所有后缀按字典序从小到大排序的结果（在字符串S的下标）。 举例：BANANA的后缀数组sa[]={5,3,1,0,4,2}，更详细点就是后缀5（A），后缀3（ANA），后缀1（ANANA）。。。
  • 名次数组：名次数组rank[i]表示++后缀i在后缀数组里的名次（在sa数组的下标）。++ 容易看出，后缀数组和名次数组为互逆运算。举例：一个字符串BANANA，rank[3]（后缀3为ANA）等于1（结合上文），逆运算：sa[1]=3。
  • 高度数组：高度数组height[i]表示sa[i]和sa[i-1]的LCP（最长公共前缀）。

求法

后缀数组

  • DA算法：倍增思想+基数排序（双关键字排序），复杂度 $O(nlogn)$
    倍增过程
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
void build_sa(int m = 128) {
    int i, j, p, *x = tmp_one, *y = tmp_two;
    //对于单字符S[i~i]的基数排序
    for (i=0; i<m; ++i) c[i] = 0;
    for (i=0; i<n; ++i) c[x[i]=s[i]]++;
    for (i=1; i<m; ++i) c[i] += c[i-1];
    for (i=n-1; i>=0; --i) sa[--c[x[i]]] = i;
    //对于长度j，关键字为(S[i~(i+j-1)],S[(i+j)~(i+j+j-1)])进行基数排序
    for (j=1, p=0; j<=n; j<<=1) {
        //直接利用sa数组排序第二关键字
        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<m; ++i) c[i] = 0;
        for (i=0; i<n; ++i) c[x[y[i]]]++;
        for (i=1; i<m; ++i) c[i] += c[i-1];
        for (i=n-1; i>=0; --i) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        //根据sa和y数组计算新的x数组
        for (p=1, x[sa[0]]=0, i=1; i<n; ++i) {
            x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++);
        }
        if ((m=p) >= n) break;
    }
}

代码解释：参数m表示不同字符的个数（会增大），数组s是字符串转换成数字数组。用到三个辅助数组，x数组记录当前长度j下后缀i的排名，y数组记录第二关键字排序的结果，c数组用来计数和定位。

参考资料

后缀数组（入门经典学习笔记）

数据结构之后缀数组

后缀数组(suffix array)详解

后缀数组的应用

单个字符串的相关问题

连续重复子串

POJ 3693 Maximum repetition substring
给定一个字符串，求重复次数最多的连续重复子串。
枚举长度 $L$，将字符串按照长度 $L$ 分块。记重复子串为$S$，$S$一定包括字符 $s[0]$，$s[L]$，$s[2L]$，… 中的某相邻两个。所以枚举两个相邻的点，往前和往后分别匹配到多远，设总长度为 $K$，那么连续出现 $K/L+1$ 次。最后求最大值即可。总时间复杂度：$O(NlogN)$