后缀数组学习笔记

最近在尝试把还没搬运的学习笔记搬运过来。

后缀数组是后缀树的优秀替代算法，与后缀自动机在字符串题中出现频率相似。其可以在$O(n\log n)$的时间内处理一类字符串后缀问题，且算法复杂度与字符集无关。

在本文中，使用$\left|s\right|$表示字符串$s$的长度。

定义（们）

后缀

$\rm {suffix}(i)$表示字符串$s$从第$i$个位置开始的子串，$i\in[0,\left|s\right|]$。

字典序

从首位开始按照ASCII码比较，若从某位开始ASCII码不相同，认为ASCII码小的所在字符串小。
若两个字符串长度不同，则认为空字符ASCII码为$-1$。
根据字典序我们可以定义字符串之间的大小关系与相同/不同关系。
显然，一个字符串的两个后缀是不同的。

最长公共前缀LCP

两个字符串$a,b$分别从起始位置延伸，使得延伸出的两个子串相同，所能延伸的最长长度。
如$ababaaa$与$ababcaa$的LCP为$4$。

后缀数组$\rm {sa}[]$

将所有后缀排好序后的结果，$sa[i]$表示第$i$小后缀在原串中的起始位置。
对应关系：名次$\Rightarrow$后缀起始位置

名次数组$\rm {rk}[]$

$rk[i]$表示$\rm {suffix}(i)$的排名。
显然有$rk[sa[i]]=i$。
对应关系：后缀起始位置$\Rightarrow$名次

高度数组$\rm {height}[]$

保存排名相邻的后缀的LCP长度。

$$\begin{aligned} \rm {height}[i]=\begin{cases}0 & i=0 \\ LCP(\rm {suffix}(\rm {sa}[i]),\rm {suffix}(\rm {sa}[i-1])) & i>0\end{cases} \end{aligned}$$

后缀数组与名次数组的构造

下面给出两种可行的构造方法：

1. 快排：$O(n^2\log n)$，字符串比较是$O(n)$的，太慢了。
2. 倍增算法：$O(n\log n)/O(n\log^2 n)$，下面我们来介绍这种算法。

利用上一次的结果，倍增计算出每个位置开始的长度为$2^k$的子串排名。
先计算出每个位置开始，长度为$2^0=1$的子串排名，例字符串$heheda$。

$s[i]$	h	e	h	e	d	a
$\rm {rank}[i]$	3	2	3	2	1	0

为了求出长度为$2^1=2$的排名，我们以每个位置$i$开始，长度为$2^0=1$的子串排名作为第一关键字$\rm {fir}[]$，以每个位置$i+2^0=i+1$开始，长度为$2^0=1$的子串排名为第二关键字$\rm {sec}[]$，进行双关键字排序：（对于$\ge n$的位置，记其排名为$-1$）

$\rm {s}[i]$	h	e	h	e	d	a
$\rm {fir}[i]$	3	2	3	2	1	0
$\rm {sec}[i]$	2	3	2	1	0	-1
$\rm {rk}[i]$	4	3	4	2	1	0

重复以上过程：

$\rm {s}[i]$	h	e	h	e	d	a
$\rm {fir}[i]$	4	3	4	2	1	0
$\rm {sec}[i]$	4	2	1	0	-1	-1
$\rm {rk}[i]$	5	3	4	2	1	0

当$\rm {rk}[]$值互不相同时，下一次排序第一关键字互不相同，故已排序完毕，可以提前退出。

若还无法理解倍增算法排序，可以参考这一段：

通过不断地倍增，利用子串组合出后缀，因为双关键字排序比字符串排序快，因此倍增算法效率很高。

双关键字排序若使用快排实现，时间复杂度为$O(n\log^2 n)$，考虑离散化后字符集大小$\le n$，故可以使用$O(n)$的基数排序实现这一过程，将时间复杂度将为$O(n\log n)$。

注：

1. 本文在叙述时排名$\in[-1,n)$，实际在代码中$\in[0,n]$。
2. 双关键字排序时先按第二关键字排序，用$\rm {tmp}[i]$记录第$i$大的第二关键字所在位置。
   再按第一关键字排序，然后$i=1\sim n$遍历$\rm {tmp}$，取出第二关键字排名，按照第一关键字所在桶倒序插入。
   这里也有其他的方式，但按照上述menci的方法简单易懂：
   
3. 因为排名可能有并列，所以先将排序结果暂存在$\rm {sa}[]$中，再根据$\rm {sa}[]$分类讨论求出$\rm {rk}[]$。

下面分段讲解构造的代码：

首先，将字符集离散化，保证字符集元素在$[1,n]$中：

sort(a+1,a+n+1);
int tot=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+tot+1,b[i])-a;

接着，计算单个字符的排名：

void fill_buc(int n,int *a) {
    fill(buc,buc+n+1,0);
    for(int i=1; i<=n; i++)buc[a[i]]++;
    for(int i=1; i<=n; i++)buc[i]+=buc[i-1];
}

fill_buc(n,a);
for(int i=1; i<=n; i++)rk[i]=buc[a[i]-1]+1;

开始倍增：

for(int t=1; t<=n; t<<=1) {

设置每个位置的第一、第二关键字：

for(int i=1; i<=n; i++) {
    fir[i]=rk[i];
    sec[i]=(i+t)>n?0:rk[i+t];
}

对第二关键字进行排序，用$\rm {tmp}[i]$记录第$i$大的第二关键字所在位置。

fill_buc(n,sec);
for(int i=1; i<=n; i++)tmp[n-(--buc[sec[i]])]=i;

对第一关键字排序，根据两次排序结果固定排名（解释见上面的注$2$），用$\rm {sa}[i]$暂存。

fill_buc(n,fir);
for(int i=1; i<=n; i++)sa[buc[fir[tmp[i]]]--]=tmp[i];

通过$\rm {sa}[]$计算$\rm {rk}[]$，并判断是否已经互不相同，可以提前退出：

1. 没有前一名，当前位置的排名为$1$。
2. 当前位置和前一名位置的第一、第二关键字均相等，当前位置的排名与前一位置的排名相等。
3. 当前位置和前一名位置的第一或第二关键字不相等，当前位置的排名为前一位置的排名$+1$。

bool unique=1;
for(int j=1,last=0; j<=n; j++) {
    int i=sa[j];
    if(!last)rk[i]=1;
    else if(fir[i]==fir[last]&&sec[i]==sec[last])rk[i]=rk[last],unique=0;
    else rk[i]=rk[last]+1;
    last=i;
}
if(unique)break;

高度数组的计算

后缀数组的应用几乎都需要用到$\rm {height}[]$，如果按照定义计算需要$O(n^2)$的时间。
如果优化求出$\rm {height}[]$的顺序，利用已知$\rm {height}$扩展未知$\rm {height}$，能否优化时间？

定义$\rm {h}[i]$表示第$i$个位置的后缀与排在其前一名的LCP长度，
即当$\rm {rk}[i]\gt 1$时：

$$\begin{aligned} \rm {h}[i]&=\text {LCP}(\rm {suffix}(i),\rm {suffix}(\rm {sa}[\rm {rank}[i]-1])) \\ &=\rm {height}[\rm {rk}[i]] \end{aligned}$$

定理：$\rm {h}(i)\ge \rm {h}(i-1)-1$

证明：

• 当$\rm {h}(i-1)<1$时显然成立。
• 当$\rm {h}(i-1)\ge1$时，说明$\rm {suffix}(i-1)$与其前一名有$ge1$的LCP。
  
  如图，$\rm {suffix}(\rm {sa}[\rm {rk}[i-1]-1]+1)$与$\rm {suffix(i)}$的LCP为$\rm {h}(i-1)-1$，而$\rm {suffix}(\rm {sa}[\rm {rk}[i-1]-1]+1)$与$\rm {suffix(i)}$在$\rm {sa}$中的距离比$\rm {suffix(i)}$与$\rm {suffix(\rm {sa}[\rm {rk}[i]-1])}$的距离更小，根据字典序的定义，后两者的LCP不会比前两者小，Q.E.D.

故我们可以按照$\rm {height}[\rm {sa}[i]]$的顺序进行递推，每次从$\rm {h}[i-1]-1$向后扩展LCP。
不难证明时间复杂度是均摊$O(n)$的。

模板

注意这里没有给出离散化的代码。

const int maxn=200005;

namespace Suffix_Array {
	int sa[maxn],rk[maxn],fir[maxn],sec[maxn],buc[maxn],tmp[maxn],height[maxn];

	void fill_buc(int n,int *a) {
		fill(buc,buc+n+1,0);
		for(int i=1; i<=n; i++)buc[a[i]]++;
		for(int i=1; i<=n; i++)buc[i]+=buc[i-1];
	}

	void build(int n,int *a) {
		fill_buc(n,a);
		for(int i=1; i<=n; i++)rk[i]=buc[a[i]-1]+1;
		for(int t=1; t<=n; t<<=1) {
			for(int i=1; i<=n; i++) {
				fir[i]=rk[i];
				sec[i]=(i+t)>n?0:rk[i+t];
			}
			fill_buc(n,sec);
			for(int i=1; i<=n; i++)tmp[n-(--buc[sec[i]])]=i;
			fill_buc(n,fir);
			for(int i=1; i<=n; i++)sa[buc[fir[tmp[i]]]--]=tmp[i];
			bool unique=1;
			for(int j=1,last=0; j<=n; j++) {
				int i=sa[j];
				if(!last)rk[i]=1;
				else if(fir[i]==fir[last]&&sec[i]==sec[last])rk[i]=rk[last],unique=0;
				else rk[i]=rk[last]+1;
				last=i;
			}
			if(unique)break;
		}
		int k=0;
		for(int i=1; i<=n; i++) {
			if(rk[i]==1)k=0;
			else {
				if(k>0)k--;
				int j=sa[rk[i]-1];
				while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;
			}
			height[rk[i]]=k;
		}
	}
}

应用

1. 求LCP
   求两个后缀的LCP，可以使用RMQ查询最小值得到。
   求$A,B$两个串子串的最大LCP（poj2774），可以将两个串拼起来得到A#B，求出$\rm {sa}[]$与$\rm {height}[]$。
   显然最大LCP在$\rm {sa}[]$中一定是相邻的，故枚举$\rm {sa}[]$，判断是否一个在#前，一个在#后，取个$\max$即可。
2. 求回文串（ural1297）
   将$s$翻转过来再插在原串后面，枚举回文中心就变成了求两个后缀的LCP，注意奇偶讨论。
   然而求回文串我们一般都用马拉车算法或回文自动机跑了。
3. 求一个串的不同子串个数（SPOJ705）
   每个后缀对答案的贡献为$n-\rm {sa}[i]+1-\rm {height}[i]$。
4. 求不重叠的子串最大LCP（「USACO5.1.3」乐曲主题）
   二分LCP长度，若有连续一段的$\rm {height}\ge mid$，检查$\max\lbrace \rm {sa}[i]\rbrace$-$\min\lbrace \rm {sa}[i]\rbrace$是否$\gt mid$，若大于说明不重叠，return true;
5. 求出现了$k$次的最长串（「USACO 2006 December Gold」Milk Patterns产奶模式）
   二分LCP长度，若有连续一段的$\rm {height}\ge mid$，检查这一段长度是否$\ge k-1$，若是，return true;

参考资料

• 后缀数组学习笔记 - Menci
• 后缀数组学习笔记 - Bill Yang笔记本旧稿