后缀数组

• 后缀数组

AHOI2013 差异 笔记 单调队列套路题。

NOI2016 优秀的拆分 题解 ( t st) 表和断点套路题。

SP8222 NSUBSTR - Substrings 代码 单调队列套路题。

CF1073G Yet Another LCP Problem 代码
后缀数组（加 ( t ST) 表）加线段树（单点修改、全树取 ( t min)、全树查询），以 (a_i) 为背景正反两方向扫。

求 (n) 个字符串最长公共连续字串。 代码
连接字符串，相邻串之间加入奇怪字符，建后缀数组和 ( t ST) 表。

//SuffixArray
int m,c[N+7],tp[N+7],rk[N+7],sa[N+7],h[N+7];
void csort(){
	for(int i=0;i<=m;i++) c[i]=0;
	for(int i=1;i<=n;i++) c[rk[i]]++;
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[rk[tp[i]]]--]=tp[i];
}
void build(){
	for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;
	m=128,csort();
	for(int w=1,p=1,i;p<n;w<<=1,m=p){
		for(p=0,i=n-w+1;i<=n;i++) tp[++p]=i;
		for(i=1;i<=n;i++)if(sa[i]>w) tp[++p]=sa[i]-w;
		csort(),swap(rk,tp),rk[sa[1]]=p=1;
		for(i=2;i<=n;rk[sa[i]]=p,i++)
			if(tp[sa[i]]!=tp[sa[i-1]]||tp[sa[i]+w]!=tp[sa[i-1]+w]) p++;
	}
	for(int i=1,j,k=0;i<=n;h[rk[i++]]=k)
		for(k=k?k-1:k,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
}