其实很久之前思想上就会了,只不过一直没有打过Orz,这两天打了一下,其实比SAM好理解多了呀
后缀数组的定义
- 将字符串s以所有位置开头的后缀排个序。
- SA[i]:排名第i的后缀的开头。
- Rank[i]:以i开头的后缀的排名。
- SA与Rank其实是互逆的。
后缀数组的求法
- 有一种比较快的DC3可以做到O(n),但是常数巨大,不推荐使用(除非出题人真的卡你)
- 所以还是老老实实用倍增吧,O(n log n),常数比较小。
- 大体方法就是得到每个位置开头长度k的,再通过基数排序(双关键字桶排)得到长度为k*2的。最终得到长度为n的(多的空字符视作最小的字符)。
int sa[maxn],rk[maxn],x[maxn],d[maxn],t[maxn],h[maxn];
int cmp(int i,int j,int k){return t[i]==t[j]&&t[i+k]==t[j+k];}
void GetSA(){
m=255;
for(i=1;i<=n;i++) t[x[i]=s[i]]++;
for(i=0;i<m;i++) t[i]+=t[i-1];
for(i=n;i>=1;i--) sa[t[x[i]]--]=i;
for(k=1;k<=n;k<<=1){
int p=0;
for(i=n-k+1;i<=n;i++) d[++p]=i;
for(i=1;i<=n;i++) if (sa[i]>k) d[++p]=sa[i]-k;
for(i=0;i<=m;i++) t[i]=0;
for(i=1;i<=n;i++) t[x[i]]++;
for(i=1;i<=m;i++) t[i]+=t[i-1];
for(i=n;i>=1;i--) sa[t[x[d[i]]]--]=d[i];
memcpy(t,x,sizeof(x));
x[sa[1]]=p=1;
for(i=2;i<=n;i++) x[sa[i]]=cmp(sa[i],sa[i-1],k)?p:++p;
if (p>=n) break; m=p;
}
for(i=1;i<=n;i++) rk[sa[i]]=i;
for(i=1,j=0;i<=n;i++) {
if (j) j--;
while (s[i+j]==s[sa[rk[i]-1]+j]) j++;
h[rk[i]]=j;
}
}
- 实现的时候先将长度为1的预处理好。
- 排序的时候记录x[i]表示以i开头的长度为k的子串在所有子串中的大小,也就是rank,可以有两个x相等。
- 我们将所有的第一关键字丢到一个桶里面计数,然后按照第二关键字从大到小枚举,对于这个位置的第一关键字,如果与其他位置的第一关键字相等,但是因为第二关键字的缘故,编号自然是在这个第一关键字对应的区间中从后往前选的。
- 所以我们需要得到第二关键字排序的顺序,首先对于i=[n-k+1,n],它们的第二关键字为空,先加进队列d里。
- 然后接下来的顺序就可以直接根据SA(因为之前已经排好了)逐个加进去了。这样就可以得到顺序了。
- 然后我们还需要得到新的x。同样按照新的SA的顺序去枚举,如果当前的排序与前一个不一样的话才cnt++。
- 实际上最后的x就是rank
后缀数组的应用
- 后缀数组有一个很重要的东西height[i],表示suffix(SA[i])与suffix(SA[i-1])的最长公共前缀。
- 对于求这个height,我们有一个结论
- 证明如下(其实随便画画图就可以得到)
设k=SA[rank[i-1]-1],height[rank[i-1]]为suffix(k)与suffix(i-1)的最长公共前缀
如果去掉这两个字符串的开头的话,得到的就是suffix(k+1) 和 suffix(i),显然suffix(k+1) 在suffix(i)的前面。
那么在i前的一定在suffix(k+1)和suffix(i)之间。所以这两个的前缀至少是height[rank[i-1]]-1。
- 所以我们只需要根据rank去求就可以了。
常规操作
- 求任意两个后缀i,j的最长公共前缀长度:height[rank[i]+1…rank[j]]的最小值
- 还有很多神奇的应用,但是我接触的不多