后缀三姐妹

后缀数组


$sa(i)$:排第$i$名的后缀
$rank(i)$:$Suffix(i)$在所有后缀中的名次

倍增法

对每个字符开始的长度为$2^k$的子字符串进行排序,求出$rank()$,当$2^k>n$后,此时的$rank()$便是最后的结果
每一次排序利用上次两个长度为$2^{k-1}$的字符串的$rank()$作为第一、第二关键字,进行基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&&(r[a+l]==r[b+l]);}//比较第一、二关键字

void DA(int n,int m=128){//n+1并人工添加一个较小的字符以避免cmp越界
int i,k,p,*x=rk,*y=rk2;
for(i=0;i<m;i++) c[i]=0;//对长度为1的字符串基数排序
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(k=1,p=1;p<n;k<<=1,m=p){//max(rank())<p
for(p=0,i=n-k;i<n;i++) y[p++]=i;//不存在第二关键字的排在前面
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;//利用上一次求得的SA对第二关键字排序
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]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
}//rank()保存在x数组中,p=不同的字符串个数
}

LCP

$height(i)$:$LCP(Suffix(sa[i]),Suffix(sa[i-1]))$
$h(i)$:$height(rank[i])$
性质:

计算

根据$h(i) \geq h(i-1)-1$逐一计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void calh(int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rk[sa[i]]=i;
for(i=0;i<n;height[rk[i++]]=k)
for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
}

void RMQ(){
for(int i=1;i<=n;i++) f[i][0]=height[i];
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

int lcp(int a,int b){
int x=rk[a],y=rk[b];
if(x>y) swap(x,y);x++;
int k=log(y-x+1)/log(2);
return min(f[x][k],f[y-(1<<k)+1][k]);
}


后缀树


大力搞搞……

notes


后缀自动机


确定性有限状态自动机

$DFA$由以下$5$部分组成

  • $alpha$:字符集
  • $state$:状态集合
  • $init$:初始状态集合
  • $end$:终止状态集合
  • $trans$:状态转移函数

$DFA$的功能是识别字符串
$SAM$本质上是一个$DFA$,可以识别$S$的所有子串

最简状态表示

现在需要把$S$建成$SAM$
考虑最简单的实现方式:将每个后缀插入一颗$Trie$树
但是这样太$naive$了,我们考虑合并状态

对于$S$的一个子串$s1$,$right(s1)=s1$在$S$中所有出现的结束位置集合
将所有$right()$集相同的状态合并

新的状态

考虑其与原先暴力表示状态的不同

  • 代表的子串:新的状态代表的子串为右端点相同,长度递增的多种子串,记长度区间为$[min(x),max(x)]$
  • 结论:状态的$right()$集合可以构成一个树形结构的关系,称其为$fail$树
    其中状态$x$在树上的父亲$fa$满足:$right(fa)\nsupseteqq right(x)$,且$|right(fa)|$最小,并有$min(x)=max(fail(x))+1$
  • 状态数:可以证明是线性的
  • 性质:一个子串的出现次数,就是其对应状态的$right()$集大小

转移函数

$trans(x,str)$为从状态$x$读入字符串$str$后到达的状态
记$ST(str)=trans(init,str)$

构造

增量法

让新加入的子串都被状态代表,而且$trans$边能够正确转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void add(int x){
int c=a[x],np=++tot,p=last;last=np;
step[np]=x;
for(;p&&!ch[p][c];p=fail[p]) ch[p][c]=np;
if(!p) fail[np]=root; else{
int q=ch[p][c];
if(step[p]+1==step[q]) fail[np]=q; else{
int nq=++tot;step[nq]=step[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fail[nq]=fail[q],fail[np]=fail[q]=nq;
for(;ch[p][c]==q;p=fail[p]) ch[p][c]=nq;
}
}
}
分享到: