后缀数组

定义

字符串s
子串：在字符串s中，取任意i<=j，那么在s中截取从i到j的这一段就叫做s的一个子串
后缀suff(i)：从字符串的某个位置i到字符串末尾的子串
后缀数组sa[i] ：表示排名为i的后缀的起始位置的下标
数组rk[i] ：表示起始位置的下标为i的后缀的排名
suff(sa[i])：表示排名为i的后缀
LCP(i, j) ： 排名为i的后缀 和 排名为j的后缀 的最长公共前缀
height[i] ： LCP(i, i-1) 排名为i 和排名为i-1的后缀 的 最长公共前缀
height[1]=0

可以解决的问题

Problem1
求一个字符串s的子串中至少出现过两次的最长的子串
Solution1
字典序相近的后缀的最长公共前缀 就是相同最长子串
也就是枚举遍历一边height[]数组，取最大

Problem2
求两个字符串的最长公共子串
Solution2
两个字符串拼接一个字符串，字典序相近的后缀的最长公共前缀 且 sa[i] 和 sa[i-1]必须在不同的字符串里面

Problem3
给定一个字符串s，求它不同的子串的个数
Solution3
每个后缀的贡献 (字符串长度-每个后缀的长度) - height[i] (重复的子串)

模版

int sa[MAXN],c[MAXN];
int rank[MAXN],height[MAXN];
void build_sa(int s[],int n,int m) {// 字符串 字符串长度+1 最大字符+1
	int i,j,p,*x=t1,*y=t2;
	for(i=0; i<m; i++)c[i]=0;
	for(i=0; i<n; i++)c[x[i]=s[i]]++;
	for(i=1; i<m; i++)c[i]+=c[i-1];
	for(i=n-1; i>=0; i--)sa[--c[x[i]]]=i;
	for(j=1; j<=n; j<<=1) {
		p=0;
		for(i=n-j; i<n; i++)y[p++]=i;
		for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0; i<m; i++)c[i]=0;
		for(i=0; i<n; i++)c[x[y[i]]]++;
		for(i=1; i<m; i++)c[i]+=c[i-1];
		for(i=n-1; i>=0; i--)sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1;
		x[sa[0]]=0;
		for(i=1; i<n; i++)
			x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
		if(p>=n)break;
		m=p;
	}
}
void getHeight(int s[],int n) {
	int i,j,k=0;
	for(i=0; i<=n; i++)rank[sa[i]]=i;
	for(i=0; i<n; i++) {
		if(k)k--;
		j=sa[rank[i]-1];
		while(s[i+k]==s[j+k])k++;
		height[rank[i]]=k;
	}
}

题目

kuangbin博客的题目

参考博客

传送门

论文博客

传送门