后缀数组
定义
字符串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;
}
}
京公网安备 11010502036488号