算法笔记——后缀数组

后缀指从某个位置开始到字符串末尾的一个子串，用suffix(i)来表示。

后缀数组(suffix array)指将s的所有后缀从小到大排序后，取其下标i放入数组中，该数组就叫做后缀数组。

排名数组指下标为i的后缀排序后的名词。

后缀数组和排名数组是互逆的，可以来回转换。

构建后缀数组有两种算法，DC3算法和倍增算法。一般n<=1e6时采用码量较小的倍增算法。此处采用倍增算法。

算法思路

对字符串从每个下标开始的长度为 $2^{k}$ 的子串进行排序，得到排名。k从0开始每次增加1，当 $2^{k}\geqslant n$ 时，从每个下标开始的长度为 $2^{k}$ 的子串都相当于其后缀suffix(i)。每次子串排序利用上一次子串的排名得到。

求解长度为 $2^{i}$ 的子串排名，将上一次rank值的第i个和第i+1个结合，再进行排序，得到新的rank值

当rank值没有相同值时已经得到了后缀排名，因为通过结合的方法前面的字符串已经确定了大小，无需再排序。

最后将rank数组转化为后缀数组，即 $suffix[rank[i]]=i;$

算法实现

后缀数组的构建中涉及到排序，因为采用倍增算法，因此长度为n的字符串最多需要 $O(logn)$ 次排序，排序若采用快速排序，则总复杂度为 $O(nlog^{2}n)$ ，而采用基数排序复杂度为 $O(nlogn)$ ，因此此处采用基数排序

1、将每个字符都转换为数字存入ss[]，并通过参数传递赋值给x[]数组（相当于排名数组），进行基数排序。为了防止比较时越界，在末尾用0封装。同时将字符串长度n+1

执行基数排序，的到后缀数组sa[]。

注意：大于等于n的部分的排名应与存在的所有排名不同，因为默认的0是有效的排名，所以将越界的排名赋为-1

//...该步将s[i]转化为初始排名ss[i]
for(int i=0;i<m;i++)    c[i]=0;
for(int i=0;i<n;i++)    c[x[i]=ss[i]]++;
for(int i=1;i<m;i++)    c[i]+=c[i-1];
for(int i=n-1;i>=0;i--)    sa[--c[x[i]]]=i;//记得倒序放入
for(int i=n;i<=2*n;i++)    x[i]=-1;

2、求解长度为 $2^{t}=2*k$ 的子串排名。

目标：根据长度 $2^{t-1}=k$ 的 $x[]$ 和 $sa[]$ 数组计算出表示长度 $2^{t}$ 的这两个数组。

（1）首先计算新的 $sa[]$

①对第2关键字进行基数排序。

重点区分：因为可能并列，排名数组位置是不重复的，而排名是可以重复的，同一个排名占据几个排位数组位置用cnt数组来统计， $cnt[i]$ 表示排名为i的占了几个排名数组位置

$x[i]$ 表示以原字符串i位置为开头，长度 $2^{t-1}$ 的子串在所有子串中的排名。 $x[i]$ 为排名数组

$sa[i]$ 表示目前在排名数组i位置，长度为 $2^{t-1}$ 的是以原字符串 $sa[i]$ 位置为开头的子串。

排序的方式是将 $x[i]$ 与第 $x[i+k]$ 结合再进行排序。那么 $x[i]$ 和 $x[i+k]$ 就分别作为基数排序的第1和第2关键字。

易得后k个（n-k~n-1）无法获取第2关键字，那么就默认其第2关键字为0

利用 $y[]$ 数组暂存以第2关键字排序的结果。

关键字0的肯定排在最前面，所以y[0~k-1]=n-k~n-1（一共k个）

int p=0;
for(int i=n-k;i<n;i++)
    y[p++]=i;

将剩下的以第2关键字排序，结果实际上就是旧的 $sa[]$ 数组中下标为1~k的内容，因为旧 $sa[]$ 保存的是旧 $x[]$ 的基数排序结果，而当前以第2关键字排序即为删除掉x[0~k-1]后的基数排序结果。因此将下标为0~k-1的结果筛去，就可以将旧 $sa[]$ 转化为 $y[]$

此时除了前面的0关键字， $y[]$ 存的都是以第2关键字下标i+k表示的结果。

②接下来要以第1关键字排序，因此在将旧 $sa[]$ 转化为 $y[]$ 时将下标-k，就可以以第1关键字的下标i来表示第2关键字的排序结果。（可以理解为对数字是通过取不同位获得其它关键字，这里通过-k获得了另一个关键字进行排序）

for(int i=0;i<n;i++)
{
    if(sa[i]>=k)//筛掉前k个
        y[p++]=sa[i]-k;//转化为第1关键字表示
}

那么此时再将 $y[]$ 转化为排名 $wv[]$ ，则正好是按照第2关键字排序后，待排序的第1关键字序列。（即当前的 $x[y[i+k]]$ 已有序， $x[y[i]]$ 待排序）

for(int i=0;i<n;i++)
    wv[i]=x[y[i]];

接下来就是把第1关键字进行基数排序，就可以得到有序的新 $sa[]$ 数组。

for(int i=0;i<m;i++)
    c[i]=0;
for(int i=0;i<n;i++)
    c[wv[i]]++;
for(int i=1;i<m;i++)
    c[i]+=c[i-1];
for(int i=n-1;i>=0;i--)//从后往前，维护排名相同的相对位置
    sa[--c[wv[i]]]=y[i];//仍然存下标

（2）计算新的 $x[]$

此时 $y[]$ 的内容已经保留到 $sa[]$ 中，已经完成了功能，因此暂存 $x[]$ 于 $y[]$ 中，以便计算新 $x[]$

只有补上的一个0的排名为0

swap(x,y);//y暂存x
x[sa[0]]=0;

用p来标记当前的排名为多少，p初值为0

那么只需要知道 $x[sa[i]]$ 什么时候需要变大就行。

比较 $y[sa[i]]$ 和 $y[sa[i-1]]$ 以及 $y[sa[i]+k]$ 和 $y[sa[i-1]+k]$ 是否相同

此处 $sa[i]+k$ 和 $sa[i-1]+k$ 可能会大于n，因此前面将大于n的排名赋为-1

但不会超太多，否则前面的语句就为false，不会调用后面的数组。

（分别表示该位与前一位第1关键字和第2关键字指向的旧排名是否一致，若都一致则说明字符串相同，新排名相同，否则新排名不同，而 $sa[]$ 已经确定了该位与前一位的顺序，不一致则排名增加即可）

注意：因为并列的不断减少，最大排名会逐渐变大，因此基数也得改变，基数应为最大排名p再+1

int p=0;
for(int i=k;i<n;i++)
    x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
m=p+1;//注意要基数改为当前最大排名

至此计算出了新的 $x[]$ 和 $sa[]$

重复此操作至 $2^{k}\geqslant n$ 时即可得到后缀数组 $sa[]$

$h[]$

最长公共前缀（LCP）

求出了 $sa[]$ 数组后， $suffix(sa[i])$ 就表示所有后缀中，排名第i的后缀。

$height[]$ 表示排名相邻的两个后缀的最长公共前缀的长度。 $height[i]$ 表示排名为i和i-1的后缀的最长公共前缀

性质1：

对于任意两个后缀suffix(i),suffix(j)，若rank[i]<rank[j],则它们的最长公共前缀长度为height[rank[i]+1],height[rank[i]+2],……,height[rank[j]]的最小值。

该性质显然成立，因此将求最长公共前缀转化为了区间RMQ问题。

计算height[]数组

首先定义一个h数组： $h[i]=height[rank[i]]$ ,根据 $rank[]$ 和 $sa[]$ 的互逆关系， $i=sa[rank[i]]$

$h[sa[rank[i]]]=height[rank[i]]$ ,令 $t=rank[i]$ ,得 $h[sa[t]]=height[t]$

发现 $h[]$ 和 $height[]$ 只是下标不同，前者使用 $sa[]$ 作为下标，后者使用 $rank[]$ 作为下标

$height[]$ 表示排名相邻的后缀的最长公共前缀

$h[]$ 表示后缀起点相邻的后缀的最长公共前缀

性质2：

h[i]>=h[i-1]-1;

有了这个性质，求解出h[i-1]，然后在h[i-1]-1的基础上继续计算h[i]即可，线性递推求解时间复杂度为 $O(n)$

证明

（1）设后缀i-1的前一名后缀为k( $k=sa[rank[i-1]-1]$ )，h[i-1]为两个后缀的最长公共前缀。后缀k表示从第k个字符开始的后缀

（2）将后缀i-1和后缀k同时去掉第一个字符，则两者变为后缀i和后缀k+1，两者之间可能存在其他后缀。后缀i的前一名后缀的最长公共前缀为h[i]，因为其他后缀排名在后缀i和后缀k+1之间，而两者前h[i-1]-1长度的前缀相同，因而夹在中间的前h[i-1]-1长度的前缀也相同。剩余部分可能与后缀i相同也可能不同，所以 $h[i]\geqslant h[i-1]-1$

void calc_height()
{
    int i,j,k=0;//k表示前一个h的值
    for(int i=1;i<=n;i++)    rank[sa[i]]=i;
    for(int i=0;i<n;i++)
    {
        if(k)    k--;//h[i]>=h[i-1]-1
        j=sa[rank[i]-1];
        while(r[i+k]==r[j+k])    k++;   
        height[rank[i]]=k;
    }
}

后缀数组应用

1、最长重复子串

重复子串指一个字符串的子串在该字符串中至少出现两次。重复子串问题包括3种类型。

（1）可重叠。给定一个字符串，求最长重复子串的长度，这两个子串可以重叠。例如，对于字符串"aabaabaac"，最长重复子串为"aabaa",长度为5。

求解最长重复字串（可重叠）的长度，等价于求两个后缀的最长公共前缀的最大值，即height数组的最大值。时间复杂度为O(n)

（2）可重叠且重叠k次。给定一个字符串，求至少出现k次的最长重复字串的长度，这k个子串可以重叠。

可以使用二分答案，二分长度l，判断是否存在k个长度为l的子串相同，将最长公共子串长度大于等于l的分为一组(若 $height[i\cdots j]\geqslant l$ ,则 i-1~j 分为一组)，查看每一组内的后缀个数是否大于等于k。例如对于字符串"aabaaaab"，求至少出现4次的最长重复子串长度，则将最长公共子串长度大于2的分组后，第1组正好重复4次，至少出现4次的最长重复子串长度为2。该算法的时间复杂度为 $O(nlogn)$

（3）不可重叠。给定一个字符串，求最长重复子串的长度，这两个子串不可以重叠。

可以使用二分答案，二分长度l，判断是否存在2个长度为l的子串相同。将最长公共子串长度大于等于l的分为一组，查看每一组内后缀的sa最大值和最小值之差是否大于等于l。因为sa是后缀的开始下标，下标差值大于等于l，说明这两个后缀必然不重叠。该算法时间复杂度 $O(nlogn)$

2、不同子串的个数

给定一个字符串，求不同子串的个数。每个子串一定都是某个后缀的前缀，原问题转化为求所有后缀之间不同前缀的个数。对于每个 $sa[i]$ ，累加 $n-sa[i]-height[i]$ 即可得到答案( $n-sa[i]$ 为改该后缀长度， $height[i]$ 为相同的前缀长度），该算法时间复杂度为 $O(n)$

3、最长回文子串

给定一个字符串，求最长回文子串的长度。可将字符串反过来连接在原字符串之后，中间用一个特殊的字符间隔，然后求这个字符串的后缀的最长公共前缀即可（即 $height[]$ 最大值）。该算法的时间复杂度为 $O(nlogn)$

4、最长公共子串

对多个字符串，求重复k次的最长公共子串，可以将每个字符串都用一个原字符串中没有的特殊字符连接起来，然后求他们的最长公共前缀，求解释要判断是否属于不同的字符串。例如，求3个字符串"abcdefg","bcdefgh","cdefghi"至少重复两次的最长公共子串，可以用特殊字符"#"将3个字符串连接在一起，需要标记每个字符属于哪个字符串，求解最长公共前缀（即 $height[]$ 最大值对应的后缀）,得到至少重复两次的最长公共子串为"bcdefg"和"cdefgh"

原文链接：https://blog.csdn.net/m0_67142204/article/details/125799178