当前位置：首页 > ai >正文

【倍增桶排序】后缀数组

ai 2025/8/22 6:21:36

前言

C++算法与数据结构本博文代码打包下载

本博文代码打包下载

后缀数组

字符串s，长度为N,rank[i]记录s[i…N-1]在所有后缀的字典序，i $∈\in$ [0,N-1]。比如：s = “bac”,则rank = {2,1,3}。s = “abbc”，则rank = {1,2,3,4}。sa[i] = x，表示s[x…n-1]的字典序是i。暴力做法,时间复杂度：O(NNlogn)。
s[i…N-1] 简记为suff(i)。

倍增优化

sb[i][len] 记录s[i…i+len-1]的字典序。长短不足补’\0’。
性质一：如果sb[i1][len] <sb[i2][len]。则sb[i1][len +len] < sb[i2][ len2 + len2]。
性质二：如果sb[i1][len] == sb[i2][len]。如N-i1 >len 且N-i2>len，则sb[i1][len+len]和sb[i2][len+len]的大小关系和sb[i1+len][len]和sb[i2+len][len]相同。
性质三：如果sb[i1][len] == sb[i2][len]。不失一般性,N-i1 == len,N -i2 > len。则 sb[i1][len+len] <sb[i2][len+len]。
$\ge N$ 时，sb[i][len]便是答案。

实现

CData有两个元素：一，iCmp当前一轮的排序依据。二，下标inx，s[i…len-1]的i。
排序 $log_2N$ 轮，每轮时间复杂度：O(NlogN)。
初始：iCmp等于s[inx]。v记录所有CData。
每轮：
对v排序。
auto v1 = v
v1[0].iCmp=1，i=2 To N-1 v1[i] = v1[i-1] + (v[i1].iCmp != v[i1-1].iCmp);
i = 0 < N
v1[i].iCmp = v1[i].iCmp*(N+1)+ x。
如果x < i+len, x = v1[i+len].iCmp;否则为0 。
时间复杂度：O(NlogNlogN)

桶排序优化

按v升序将sa[inx+len]放到sa[inx]中。 v由于已经是升序，故各桶内部无需排序。每轮时间复杂度：O(N)，总时间复杂度：O(NlogN)。

DC

人言:DC算法可以将时间复杂度降低到O(n)，以后再学习。

典型应用:最长重复子串

就是所有后缀的最长公共前缀。
lcp(i,j) 是suff(rank(i))和suff(rank(j))的最长公共前缀。
性质四： $\le j \le k$ ，如果lcp(i,k)是len，lcp(j,k) $≥\ge$ len。否则，令第x个字符不同，如果前者的第x个字符小于后者的第x个字符，则前者的字典序应该小于i；如果前者的第x字符大于后者的第x个字符，则后者的字典序大于k。
推论一： $\le j1 \le j2 \le k$ lcp(j1,j2) $≥\ge$ lcp(i,k)。
推论二(LCP Lemma)： $i < j < k$ , $l c p (i, k) = min (l c p (i, j), l c p (j, k))$ 。根据推论一： $\ge lcp(i,k)$ 。 $x = min (l c p (i, j), l c p (j, k)) > l c p (i, k)$ 不成立。 $\cdots j$ 之间至少有公共前缀x， $j⋯kj\cdots k$ 之间至少有公共前缀x。故i,j至少有公共前缀x。
推论三(LCP Theorem)： $\le \min_{k:i+1}^j lcp(k,k-1)$ 。用数学归纳法证明： $j - i = 1$ 时，符合。当 $j - i = l e n 1$ 时成立，则 $j = l e n 1 + 1$ 也成立，就是推论二，对应参数分别为(i,i+len1,j)。
推论四(LCP Corollary)：对i≤j<k，LCP(j,k) $≥\ge$ LCP(i,k)。利用推论三容易证明。
小结一：求最大lcp,只需要比较字典序相邻的后缀。
性质五：不存在相等的后缀，因为两者长度不一样。
height[0]=0,height[i] = lcp(i,i-1)。 $max⁡(height)\max(height)$ 便是答案。
h[i]=h[rank[i]]。
性质六： $\ge h[i-1]-1$ 。
当 $\le 1$ 时，显然成立。
下面讨论 $h [i - 1] > 1$
$j = i - 1, k = s a [r ank [j] - 1]$
显然有：suff(k) < suff(j),即rank[k] < rank[j]。
根据性质六一：
lcp(rank(j),rank(k)) = lcp(rank(i),rank(k+1))+1
即：lcp(rank(i),rank(k+1)) = lcp(rank(j),rank(k))-1 = h[i-1]-1
根据性质六二及rank[k] < rank[j]。
rank[k+1] < rank[i],即rank[k+1] $≤\le$ rank[i]-1
根据推论四： h[i] = lcp(rank[i],rank[i]-1) $≥\ge$ lcp(rank(i),rank(k+1)）得证
性质六一： $l c p (r ank (i), r ank (j)) > 1$ 。则lcp(rank(i),rank(j))= lcp(rank(i+1),rank(j+1))+1。
sa[rank[i]-1]
性质六二： $l c p (r ank (i), r ank (j)) > 1$ 。suff(i)< suff(j)，则suff(i+1)<suff(j+1)。
小结二：i从小到大计算h[i],h[i] = max(h[i-1]-1,0)开始枚举，无需复位，只需要每次减少n。故时间复杂度O(n)。h[0]从0开始枚举。

后缀树

这个更复杂，以后研究。

代码

模板代码

class CSuffArr {public:CSuffArr(const string& str) :N(str.length()), m_str(str) {const int M = max(N, 26)+1;vector<vector<pair<int,int>>> bucket(M);	for (int i = 0; i < N; i++) {			bucket[str[i]-'a'+1].emplace_back(i, 1);}BucketToRes(bucket);for (int len = 1; len < N; len *= 2) {bucket.assign(M,vector<pair<int,int>>());for (int i = N - len ; i < N; i++) {//长度小于等于lenbucket[m_rank[i]].emplace_back(i,0);}for (const auto& i : m_sa) {if (i >= len) {const int iPre = i - len;bucket[m_rank[iPre]].emplace_back(iPre,m_rank[i]);}}BucketToRes(bucket);}}

模板题：力扣1044

核心代码

	class Solution {public:string longestDupSubstring(string s) {CSuffArr suffArr(s);auto h = suffArr.GetH();const int iMaxInx = max_element(h.begin(), h.end()) - h.begin();return s.substr(iMaxInx,h[iMaxInx]);}};

单元测试

string s;TEST_METHOD(TestMethod11){s = "banana";auto res = Solution().longestDupSubstring(s);AssertEx(string("ana"), res);}TEST_METHOD(TestMethod12){s = "abcd";auto res = Solution().longestDupSubstring(s);AssertEx(string(""), res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功