后缀数组 | Berwyn's Blog

摘要

本文介绍后缀数组的基本概念、方法以及应用

概念：

构造后缀数组的倍增算法——$O(nlogn)$
最长公共前缀LCP(Longest Common Prefix)
height数组——$O(n)$

应用：

多模式串匹配
最长回文串

比较：

后缀树与后缀数组

基本概念

字符集——$\Sigma$表示，代表了一个全序关系集合，里面任意两个不同元素可以比较大小
字符串——n个字符顺序排列而成的数组
子串——$S[i..j], i \le j$ 表示S串从i到j这一段
后缀——表示从i开始到结尾的子串
字典序——如果前面都一样一直比较不出来结果，那么长度小的字典序小
结尾字符$——对于字符串S来说
- len(S)=n
- S[n]=’$’
- $小于任何字符
后缀数组SA
- 一维数组
- $Suffix(SA[i]) < Suffix(SA[i + 1]), 1 \le i < n$
名次数组Rank
- $Rank = SA^{-1}$即$若Rank[i] = j，则SA[j] = i$
- 给定字符串下标，输出在该后缀的名次

构造方法

倍增算法，利用后缀之间的联系，复杂度由$O(n^2)$降至$O(nlogn)$

首先定义k-前缀:

$\begin{equation} u^k = \begin{cases} u[1\dots k] &len(u) \ge k \\ u &len(u) < k \end{cases} \end{equation}$

用$<_k, =_k, \le_k$表示两者k前缀的字典序大小关系

性质：

对于$k \ge n, Suffix(i) \le_k Suffix(j)$等价于$Suffix(i) < Suffix(j)$
- k已经超出总体长度了，有没有k限制当然无所谓
$Suffix(i) =_{2k} Suffix(j)$等价于$Suffix(i)=_kSuffix(j)$且$Suffix(i + k)=_kSuffix(j + k)$
- 前2k个字符相当，掰成两半比较，分别相等，没毛病
$Suffix(i)<_{2k}Suffix(j)$等价于$Suffix(i)<_kSuffix(j)$或($Suffix(i) =_kSuffix(j)$且$Suffix(i+k)<_kSuffix(j+k)$)
- 如果前2k个字符整体比较小，那么就是前k个字符小了，或者前k个字符相等比较持续到k个字符之后后k个小

定义

k-后缀数组$SA_k$——保存k-前缀比较关系的从小到大排序
k-名词数组$Rank_k$——k-后缀数组的逆

结合性质2和3，可以吧Suffix的排序转化为——每个 $Suffix_{2k}(i)$有一个主关键字 $Rank_k[i]$和一个次关键字 $Rank_k[i+k]$

构造步骤

用$SA_k$和$Rank_k$构造出$SA_{2k}$
- 基数排序$O(n)$
- 其他排序$O(nlogn)$
通过$SA_{2k}$在O(n)时间内构造$Rank_{2k}$
通过快排用$O(nlogn)$的时间构造$SA_{1}$启动整个递推流程
整体时间复杂度$O(nlogn)$

最长公共前缀

要发挥后缀数组的全部威力，需要借助LCP工具
LCP = Longest Common Prefix

定义:

对于字符串u,v定义函数$lcp(u, v) = max\{i | u =_i v\}$
对于正整数i,j定义函数$LCP(i, j) = lcp(suffix(SA[i]), suffix(SA[j]))$

性质:

LCP(i, j) = LCP(j, i)
LCP(i, i) = n - SA[i] + 1

这两个性质可以让我们计算LCP(i, j)的时候只考虑i < j的情况

直接计算LCP复杂度为O(n)，需要进行预处理简化计算复杂度

首先推倒两个性质

LCP Lemma

对于任意$i < j < k, LCP(i, k) = min(LCP(i, j), LCP(j, k))$

证明详见¹

LCP Theorem

$LCP(i, j) = min\{LCP(k - 1, k)| i + 1 \le k \le j\}$

利用数学归纳法可证

LCP Corollary

对于任意$i < j < k, LCP(j, k) \ge LCP(i, k)$

height数组

定义一维数组height, 令$height[i] = LCP(i - 1, i), 1 < i \le n$

则根据LCP Theorem，$LCP(i, j) = min(height[k]| i + 1 \le k \le j)$，当height是固定的时候，转化为标准的RMQ问题（Range Minimum Query）

RMQ问题可以通过线段树解决O(nlogn)预处理，O(logn)查询

到此，问题转化为了如何高效的求取height数组

为了描述方便定义: h[i] = height[Rank[i]]，这里的i是字符串的字符下标

h数组有如下性质:
对于$i > 1且Rank[i] > 1$一定有$h[i] \ge h[i - 1] - 1$

数学证明详见¹，罗穗骞的文章²证明更加通俗易懂一些

这个性质翻译过来就是——求h[i]时，前h[i - 1] - 1个字符都不用比较了

利用这个性质可以依如下步骤求h[i]:

如果Rank[i] = 1则h[i] = 0
若i = 1或h[i - 1]<=1直接暴力求
以上两种情况都不是的情况下即i > 1 且 rank[i] > 1且 h[i - 1] > 1的情况下根据性质3可以直接从第h[i - 1]个字符开始比较求得h[i]
可以O(n)复杂度构造h数组
然后用O(n)的时间根据height[i] = h[SA[i]]构造height数组
结合RMQ方法(O(nlogn)预处理O(n)查询)计算任意LCP(i, j)
根据lcp(Suffix(i), Suffix(j)) = LCP(Rank[i], Rank[j])

应用

个单字符串的相关问题

通常是先求height数组，利用height数组进行求解

重复子串

可重叠的最长重复子串
- 根据LCP定义，该问题等价于求height数组的最大值
不可重叠的最长重复子串
- 二分答案，转化问题为是否存在长度为K的不可重叠重复子串
- 然后根据height值进行分组，不小于k的分为一组，根据LCP的定义(取区间内的height较小者)，则每一组的LCP都不小于k
- 检查每一组的SA最大值和最小值，如果相差不小于k则存在
可重叠的k次最长重复字符串
- 和上题思路差不多，也是先分组，不同的是不用判断SA的最大差值，转而判断组内元素个数，如果大于k个则成立

不相同的子串个数

给定一个字符串，求不相同的子串的个数
把每个子串看作是某一个后缀的前缀（这样做是可以利用LCP概念）
那么每多一个后缀Suffix(SA[i])就有n - SA[i] + 1(即len(Suffix(SA[i])))个前缀
但是新加入的字符串Suffix(SA[i])和前面i - 1个后缀字符串有前缀相同
根据LCP Corollary，Sufffix(SA[i])与前面所有后缀字符串的LCP最大值为height[i],即有height[i]个前缀字符串相同
所以每加入Suffix(SA[i])，得到的新的子串的数量为n - SA[i] + 1 - height[i]
不断累加即可，复杂度为O(n)

最长回文子串问题

以最长奇回文串为例：

暴力求的话复杂度为$O(n^2)$
首先枚举中心位置
构造S串
- 在原来的字符串后面添加字符’#’(不等于原字符串的任意一个字符)
- 翻转原字符串拼接在’#’后面
- 在最后添加一个小于前面所有字符的’$’

在枚举每个中心点i后可以在T’串中找到对应点i’(2n - i)，然后通过LCP(Rank(i), Rank[i - 1])可以快速求得以i为中心的最长回文串长度
总体复杂度是预处理时间O(2nlog2n) + n次常数查询O(n) = O(nlogn)

连续重复子串

字符串L是由某个字符串S重复R次而得到的

给定字符串L，已知这个字符串是某个字符串S重复R次而得到的，求R得最大值
- 穷举字符串S的长度K
- 判断是否成立时先看L的长度能否被K整除
- 可以的话看LCP(Rank[1], Rank[1 + k])是否等于n - k，等于的话说明成立
给定一个字符串，求重复次数最多的连续重复子串
- 穷举字符串S的长度K
- 计算r = LCP(Rank[k i], Rank[k (i + 1)]), 用r / k + 1更新答案
- 整体复杂度O(nlogn)（调和级数）

两个字符串的问题

通用做法是先连接两个字符串，然后求后缀数组和height数组解决问题

公共子串

如果字符串L同时出现在字符串A和字符串B中，则称字符串L是字符串A和字符串B的公共子串

字符串中的任何子串都可以看做某个后缀的前缀，从而利用LCP高效解决

把两个字符串拼接在一起，中间用没出现过的字符隔开
求LCP最大值——等同于求height的最大值
由于是两个字符串的最大前缀，所以要求SA[i]和SA[i - 1]分属于不同的字符串即可
复杂度O(|A| + |B|)

子串个数

求长度不小于k的子串的个数

例A=“xx”，B=“xx”，k=1，长度不小于 k 的公共子串的个数是 5

把两个字符串拼接在一起，中间用没出现过的字符隔开
按height值不小于k分组
每个组中顺序扫描，每遇到一个B的后缀，结果加上前面A的后缀的数量，每遇到一个A的后缀，结果加上前面B的后缀的数量

多个字符串问题

通常是把所有字符串连起来，然后计算height数组，可能需要二分答案

不少于k个字符串的最长子串

把所有字符串连到一起，用不同的没有出现过的字符分开
二分最长子串的长度
计算height数组，按数height的值分组
判断是否有组中的字符串来自不少于k个原串
复杂度O(nlogn)

每个字符串中至少出现两次且不重叠的最长子串

把所有字符串连到一起，用不同的没有出现过的字符分开
二分最长子串的长度
计算height数组，按数height的值分组
判断是否每个原串都能在组中的找到两个子串
如果有不重叠的要求，那么还需要判断这两个子串的下标间隔不小于目前搜索的长度
复杂度O(nlogn)

出现或反转后出现在每个字符串的最长子串

先把每个字符串各自反转一遍与原串拼在一起，用不同的且没有出现过的字符分开
然后再把这些串拼在一起，同样用不同的且没有出现过的字符分开
接下来的事情差不多，二分答案，按height排序，检查每组是否满足要求，不再赘述

多模式串的模式匹配

匹配串长度为n，模式串P长度为m
如果只有一个模式串，使用KMP，复杂度为O(n + m)

多个模式串优化：

利用SA数组，用二分查找法查找匹配串后缀中与模式串公共前缀最长的后缀
复杂度变为O(mlogn)
利用LCP可以简化Suffix(SA[mid])和模式串的比较过程如下：
- 用max_match存储截止目前与P的最长公共前缀长度
- 若LCP(mid, ans) < max_match则Suffix[mid]和P的公共前缀长度就是LCP(mid, ans)那么只要比较下一个字符确定两个串的大小关系即可
- 若LCP(mid, ans) $\ge$ max_match则Suffix[mid]和P的前max_match个字符是相同的，比较直接从max_match+1开始就好
- 复杂度优化为O(m + logn)

与后缀树的比较

优点:

后缀数组比较容易理解，也易于编程实现
不需要涉及指针操作，调试方便
占用空间比后缀树要小（4n个整数 vs 4n个指针 + 2n个整数）
复杂度与字符集的复杂程度无关

缺点:

当字符集的复杂度较小时，效率不如后缀树
可以看做后缀数组叶节点的集合，需要配合LCP（在后缀树中代表两个叶节点的最近公共祖先）才能发挥威力

代码实现

参考²

bool isEqual(vector<int>* rank, int index1, int index2, int str_len) {
    return (*rank)[index1] == (*rank)[index2] && (*rank)[index1 + str_len] == (*rank)[index2 + str_len];
}

void buildSA(const vector<int>& array, vector<int>& SA, int max_rank) {
    max_rank = max(max_rank, (int)array.size());
    vector<int> bucket(max_rank, 0);
    vector<int> rank(array.size(), 0);
    //建立SA_1
    for(int i = 0; i < array.size(); ++i) {
        ++bucket[rank[i] = array[i]];
    }
    for(int i = 1; i < bucket.size(); ++i) {
        bucket[i] += bucket[i - 1];
    }
    for(int i = array.size() - 1; i >= 0; --i) {
        SA[--bucket[rank[i]]] = i;
    }
    //倍增建立SA_2*i
    vector<int> rank2(array.size());
    vector<int>* x = &rank;
    vector<int>* y = &rank2;
    for(int str_len = 1, rank_index = 1; rank_index < array.size(); str_len *= 2, max_rank = rank_index) {
        //第二关键字排序
        //没有第二关键字的pair排在前面
        rank_index = 0;
        for(int i = array.size() - str_len; i < array.size(); ++i) {
            (*y)[rank_index++] = i;
        }
        //后面的顺序往后排
        for(int i = 0; i < array.size(); ++i) {
            if(SA[i] >= str_len) {
                (*y)[rank_index++] = SA[i] - str_len;
            }
        }
        //第一关键字排序
        //根据第二关键字的排序结果重构数组，确保排序靠后的在数组后面
        vector<int> rank_value(array.size());
        for(int i = 0; i < max_rank; ++i) {
            bucket[i] = 0;
        }
        for(int i = 0; i < array.size(); ++i) {
            rank_value[i] = (*x)[(*y)[i]];
            ++bucket[rank_value[i]];
        }
        for(int i = 1; i < max_rank; ++i) {
            bucket[i] += bucket[i - 1];
        }
        for(int i = array.size() - 1; i >= 0; --i) {
            SA[--bucket[rank_value[i]]] = (*y)[i];
        }
        swap(x, y);
        (*x)[SA[0]] = 0;
        rank_index = 1;
        for(int i = 1; i < array.size(); ++i) {
            (*x)[SA[i]] = isEqual(y, SA[i], SA[i - 1], str_len) ? rank_index - 1: rank_index++;
        }
    }
}

void buildHeight(const vector<int> array, const vector<int>& SA, vector<int>& height) {
    //先根据SA构造Rank
    vector<int> rank(SA.size());
    for(int i = 0; i < SA.size(); ++i) {
        rank[SA[i]] = i;
    }
    height[0] = 0;
    for(int i = 0, j = 0, begin_shift = 0; i < SA.size() - 1; height[rank[i++]] = begin_shift) {
        for(j = SA[rank[i] - 1], begin_shift?begin_shift--:0; array[i + begin_shift] == array[j + begin_shift]; ++begin_shift);
    }
}

引用

¹. 许智磊《后缀数组》 ↩

². 罗穗骞《后缀数组——处理字符串的有力工具》 ↩