后缀数组

字符串入门算法，碰到过好多次了，一直没学，今天来拾掇一下。

实现

这里不赘述实现原理，想知道的可以去看 罗穗骞的论文 后缀数组——处理字符串的有力工具

一、倍增实现 O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
using namespace std;

//sa[i]表示排名为i的后缀suffix(id),rk[i]表示后缀suffix(i)的排名
//ht[i]表示排名为i和i-1的后缀的lcp长度
const int N=200050;

char s[N];
int sa[N],rk[N],oldrk[N<<1],id[N],px[N],cnt[N],ht[N];
bool cmp(int x,int y,int w){
	return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
void get_sa(char *s,int len){
	memset(cnt,0,sizeof cnt);
	//如果是多组数据需要特别注意这边的复杂度
	int i,n,m=len+1,p,w;
    //桶的上界可能达到len+1，注意修改m的值
	n=len;
	for(i=1;i<=n;i++)++cnt[rk[i]=s[i]];
	for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;
	for(w=1;;w<<=1,m=p){
		for(p=0,i=n;i>n-w;i--)id[++p]=i;
		for(i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
		memset(cnt,0,sizeof cnt);
		//如果是多组数据需要特别注意这边的复杂度
		for(i=1;i<=n;i++)++cnt[px[i]=rk[id[i]]];
		for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(i=n;i>=1;i--)sa[cnt[px[i]]--]=id[i];
		memcpy(oldrk,rk,sizeof rk);
		//如果是多组数据需要特别注意这边的复杂度
		for(p=0,i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
		if(p==n){
			for(int i=1;i<=n;i++)sa[rk[i]]=i;
			break;
		}
	}
	int j;
	for(i=1,j=0;i<=len;i++){
		if(j)--j;
		while(s[i+j]==s[sa[rk[i]-1]+j])++j;
		ht[rk[i]]=j;
	}
}
int ST[N][21];
void lcp_init(int len){
	int N=len;
	for(int i=1;i<=N;i++)ST[i][0]=ht[i];
	for(int j=1;j<=20;j++){
		for(int i=1;i<=N;i++){
			if(i+(1<<j)-1<=N)ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
		}
	}
}
int get_lcp(int i,int j,int len){
	if(i==j)return len-i+1;
	if(rk[i]>rk[j])swap(i,j);
	int L=rk[i]+1,R=rk[j];
	int t=log2(R-L+1);
	return min(ST[L][t],ST[R-(1<<t)+1][t]);
}

二、DC3 O ( n ) O(n) O(n) 常数比较大
三、SA-IS O ( n ) O(n) O(n) 常数较小
（这两种实现方式，之后再补，不是很会

经典trick

例1、最长公共前缀
两个后缀的最长公共前缀，就是两个后缀排名之间的 h e i g h t height height数组之间的最小值。
可以用RMQ实现， O ( n l o n g ) O(nlong) O(nlong)预处理， O ( 1 ) O(1) O(1)查询
例2、可重叠最长子串
求最长重复字串，两个子串可重叠。
子串就是后缀的一个前缀，问题等价于求两个后缀的最长公共前缀的最大值，即 h e i g h t height height数组的最大值
例3、不可重叠最长子串（poj1743）
二分答案，对于每个二分出来的值 k k k，将 h e i g h t height height数组分组，判断一个组内原下标的最大值 减 原下标的最小值，是否 > = k >=k >=k。
例4、可重叠的 k k k次最长重复子串(poj3261)
二分答案，对于每个二分出来的值 k k k，将后缀分组，判断是否存在一组内后缀的个数 > = k >=k >=k，如果有，即存在。
例5、不相同子串的个数（spoj694、spoj705）
每个子串是某个后缀的前缀，问题等价于所有后缀之间不相同的前缀的个数，那么每个后缀对答案的贡献就是 n − s a [ k ] + 1 − h e i g h t [ k ] n-sa[k]+1-height[k] n−sa[k]+1−height[k]，按排好序的后缀对答案加贡献。
例6、最长回文子串（ural1297）
将原串反转过来拼接到原串后面，中间用一个特殊字符隔开。
那么奇数长度和偶数长度的回文子串都能够通过枚举中心位置得到；对于一个中心位置，最长回文子串就是两个特定的后缀的最长公共前缀。详细见图：

例7、连续重复子串（poj2406）
给定一个字符串 L L L，已知这个字符串是由某个字符串 S S S重复 R R R次得到的，求 R R R的最大值；
枚举 S S S的长度 k k k，首先判断 L L L是否整除 k k k，再看 s u f f i x ( 1 ) suffix(1) suffix(1)和 s u f f i x ( k + 1 ) suffix(k+1) suffix(k+1)的最长公共前缀是否等于 n − k n-k n−k。因为询问的一个后缀是固定的， 那么预处理可以变成 O ( n ) O(n) O(n)，总复杂度就是 O ( n ) O(n) O(n)的。
例8、重复次数最多的连续重复子串（poj3693）
枚举长度 L L L，求长度为 L L L的子串最多能连续出现几次。连续出现一次肯定可以，所以只考虑至少两次的情况。假设在原字符串连续出现了两次，那么肯定包括了字符 s [ 0 ] s[0] s[0]、 s [ L ] s[L] s[L]、 s [ 2 ∗ L ] s[2*L] s[2∗L]…中的某相邻的两个。所以只需要看字符 s [ L ∗ i ] s[L*i] s[L∗i]和 s [ L ∗ ( i + 1 ) ] s[L*(i+1)] s[L∗(i+1)]往后能匹配多少，因为枚举的起点前面可能还有少许字符能看做是第一个重复子串里的。
假设从 s [ L ∗ i ] s[L*i] s[L∗i]开始，匹配了 k / L k/L k/L个重复子串，还剩余了 k%L 个字符，那么如果要让循环次数+1， s [ L ∗ i ] s[L*i] s[L∗i]前面还要有 L-k%L 个字符完成匹配。那么只要再check一下两个关键点前面 L-k%L的两个后缀的最长公共前缀是否比 L L L小即可。
例9、最长公共子串（poj2774）
将两个字符串拼接起来，中间用特殊字符隔开；
因为两个后缀的最长公共前缀是在后缀排名之后，一段区间的最小值，那么我们只要 f o r for for一遍后缀排名，如果前后两个后缀属于两个不同的串，就和 a n s ans ans取max，即得到答案。
例10、长度不小于 k k k的公共子串的个数(poj3415)
给定两个字符串，求三元组 ( i , j , k ) (i,j,k) (i,j,k)，从A的第i位和B的第j位，长度为k的字符串相同的个数。
将两个字符串连起来，中间用特殊字符隔开，按 k k k分组后，接下来就是快速的统计每组中后缀之间的最长公共前缀之和。扫描一遍，每遇到一个B的后缀就统计与前面的A的后缀能产生多少个长度不小于 k k k的公共子串，A的后缀需要用单调栈维护；然后对A也做一次。
例11、不小于 k k k个字符串中的最长子串（poj3294)
将 n n n个字符串连起来，中间用不相同且没出现过的字符隔开，然后二分答案，将后缀分组，判断每组内不同的字符串个数是否不小于 k k k。
例12、每个字符至少出现两次且不重叠的最长子串（spoj220）
将 n n n个字符串连起来，中间用不相同且没出现过的字符隔开，然后二分答案 k k k，将后缀分组，判断每个组内，是否每个原字符串后出现了两次，并且后缀之间的距离不小于 k k k。
例13、出现或反转后出现在每个字符串中的最长子串（poj3294）
先将每个字符串都反过来写一遍，中间用一个互不相同且没有出现的字符隔开，再将 n n n个字符串全部连起来，二分答案，将后缀分组，看一组内在每个原来的字符串或反转后的字符串中出现。

之后补上代码），有了这些小 t r i c k trick trick，遇到题目，再加上一些小想法，就能AC啦！

例题

之前碰到过好几道后缀数组的题目。
之后附上~