后缀数组

学了这个东西字符串水平下降一万倍，之前敢拿hash草的题现在不敢了。

后缀数组

板题

后缀数组可以把字符串的所有后缀存起来，然后干各种奇怪的事情。

现在给你一个字符串 banana，给他的后缀A,NA,ANA,NANA,ANANA,BANANA

跑一个后缀的trie。

然后把字典序小的字母排在左边，给每个后缀对应的叶节点标一下这个后缀首字母在文本串的位置。

从左到右连接下标就是后缀数组，比如这个的后缀数组是 \(5,3,1,0,4,2\)。实际意义：sa[1]=3 表示第3+1=4个字母开头的后缀 ANA 在所有后缀中的字典序为1，sa[3]=0 就是 BANANA 的字典序为3。

int cnt[MAXN],lsa[MAXN],lrk[MAXN];
int sa[MAXN],rk[MAXN],hei[MAXN];
void getSA(){
	m=128;
	for(int i=1;i<=n;i++)cnt[rk[i]=txt[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
	int p=0;
	for(int k=1;k<n;k<<=1,m=p){
		int cur=0;
		for(int i=n-k+1;i<=n;i++)lsa[++cur]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)lsa[++cur]=sa[i]-k;
		memset(cnt,0,sizeof cnt);
		for(int i=1;i<=n;i++)cnt[rk[lsa[i]]]++;
		for(int i=1;i<=m;i++)cnt[i] += cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[lsa[i]]]--]=lsa[i];
		for(int i=1;i<=n;i++)lrk[i]=rk[i];
		p=0;
		for(int i=1;i<=n;i++){
			if(lrk[sa[i]]==lrk[sa[i-1]] && lrk[sa[i]+k]==lrk[sa[i-1]+k])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	}
}
inline void getH(){
	for(int i=1;i<=n;i++)rk[sa[i]]=i;
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==1)continue;
		if(k)--k;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&txt[i+k]==txt[j+k])++k;
		hei[rk[i]]=k;
	}
}

板题代码。

字符加密

相当于给后缀拼上前缀排序，我们可以直接给字符串扩一倍复制一下拿新的后缀跑后缀排序，找前 \(n\) 位的后缀数组输出即可。

不同子串个数

这个要涉及到SA的一种用法叫最长公共前缀。用 \(height_i\) 表示 \(sa_{i-1}\) 和 \(sa_i\) 的最长公共前缀长度。令 \(j,k\) 为两个前缀，\(jj<k,rank_j<rank_k\)，则 \(j,k\) 的lcp 长度 \(min\{ height_{rank[j+x],x\in[1,k-j]}\}\)
。

这个就非常牛逼了。上面的码已经写了怎么求这个数组。

在本题中对于排好序的两个后缀他俩的 \(height\) 即后缀的最长公共前缀长度可以反映出他俩间贡献的相同子串个数，如图中后缀 aaaab 和 aaab 的 \(height=3\)，则有 a,aa,aaa 三个相同子串。

\(Ans=n+\binom{2}{n}-\sum height_i\)

Que：求一个字符串的最长回文串长度。

提出技巧：在原串后加入一个分隔符 {，在复制一份颠倒的字符串拼接到后面跑后缀数组。

进而一旦出现回文串就一定存在一个原串部分的后缀和一个新串部分的后缀有 LCP，取height最大值即可。

公共串

对刚才那个技巧的延伸。

可以把所有串拼成一个大串，分隔符就是 '{'+i，加是因为分隔符一样会影响后缀排序。

从 \(height\) 上考虑这个问题，相当于找到一个 \(height\) 连续段，这个段上的后缀恰好在每个原串中都有分布，现在求出每个合法段的 \(max\{min_{i=l}^r height_i\}\)。根据答案分布希望合法段越短越好，就可以用双指针维护区间，右边塞左边删到不能删之后与 \(height\) 区间上取极值，用rmq解决。

Sandy的卡片

和上一道题是一样的，界定相同串的规则变成了差值相同，维护查分数组的SA即可，最后答案+1。

喵星球上的点名

长的很ac自动机的一道题，但是我不会ac机。

先按套路把文本串赋id后拼长串跑SA。可以发现对于一次点名可以二分找出后缀序列中字典序和模式串满足权值偏序的转折点，进而考虑对模式串 \(p\) 找大于等于的后缀位置 \(L\) 和大于的后缀位置 \(R\)，区间 \([L,R]\) 内的后缀一定包含 \(p\)。

进而问题一转化成处理后的区间 \([L,R]\) 内的 \(id\) 数，可以用莫队解决。问题二则可以在莫队添删元素的时候维护。添删的时候加减上之后的询问数即可。

差异

在 \(\binom{2}{n}\) 个子串中每个后缀会被加 \(n-1\) 次。问题简化为求全后缀对LCP之和。

序列上的全点对问题极值可以用单调栈的套路处理，就是维护每个后缀成为答案贡献点的最长左右延伸，判定用 \(<\) 而不是 \(\le\) 不然要算重。