SA-IS

2020/05/02 12:00
阅读数 91

一些准备工作

为了防止一些分类讨论我们在\(s\)的末尾加一个$,假定$是最小的字符。
\(rank_i\)表示\(\operatorname{suf}_i\)的排名,\(sa_i\)表示排名为\(i\)\(\operatorname{suf}\)的起始位置。
定义一个后缀\(\operatorname{suf}_i\)为S型后缀当且仅当\(\operatorname{suf}_i<\operatorname{suf}_{i+1}\),否则就是L型后缀。我们认为$是S型后缀。
定义LMS后缀为\(\operatorname{suf}_{i-1}\)为L型后缀且\(\operatorname{suf}_i\)为S型后缀的所有\(\operatorname{suf}_i\)
定义LMS子串为相邻两个LMS后缀\(\operatorname{suf}_i,\operatorname{suf}_j\)间的\([i,j)\)这部分子串。
定义LMS前缀为从当前位置到从当前位置开始的第一个LMS型后缀这一区间构成的子串。
我们可以得到几个trivial的小结论:
\(1.\)\(s_i=s_{i+1}\),那么\(\operatorname{suf}_i,\operatorname{suf}_{i+1}\)类型相同。
\(2.\)\(s_i=s_j\)\(\operatorname{suf}_i\)是S型后缀而\(\operatorname{suf}_j\)是L型后缀,则\(\operatorname{suf}_j<\operatorname{suf}_i\)
\(3.\)LMS后缀的个数不会超过\(\frac n2\)
\(4.\)LMS子串的长度总和不会超过\(n\)
用左/右来表达一个\(\operatorname{suf}\)的起始位置与另一个\(\operatorname{suf}\)的起始位置在原串中的左/右关系,用前/后表达一个\(\operatorname{suf}\)和另一个\(\operatorname{suf}\)的大小关系。










基本流程

假如已经得到各个LMS后缀的大小关系,因为每个LMS后缀左侧的L型后缀是递增的,而右侧的S型后缀是递减的,所以可以多路归并。这种方法叫诱导排序。
要得到LMS后缀的大小关系,可以先得到各个LMS子串的大小关系,然后进行离散化得到一个新串,再求新串的SA。而给各个LMS子串排序也是一个诱导排序。

SAIS

\(n\)是串长,\(m\)是字符集大小,\(s\)是要进行后缀排序的串,\(t\)用来表示每个\(\operatorname{suf}_i\)的后缀类型(1-L,0-S),\(pos\)用来储存每一个LMS后缀的位置。

void SAIS(int n,int m,int*s,int*t,int*pos)

首先预处理出\(t,pos\)等数组,\(N\)表示新串的长度即LMS后缀的个数,\(M\)表示新串的字符集大小即本质不同的LMS子串个数,\(S\)表示新串,\(rank\)表示\(\operatorname{suf}_i\)是第几个LMS后缀(如果不是那么就为\(0\))。

int N=0,M=rank[1]=0,*S=s+n;
t[n]=0;
for(int i=n-1;i;--i) t[i]=s[i]^s[i+1]? s[i]>s[i+1]:t[i+1];
for(int i=2;i<=n;++i) rank[i]=t[i-1]&&!t[i]? pos[++N]=i,N:0;

接下来调用诱导排序给LMS子串排序,注意到我们只需要保证\(\operatorname{suf}_i\)为LMS后缀的\(i\)位置之间的相对大小符合以其为首的LMS子串的相对大小即可。过程我们之后细讲。诱导排序完之后\(sa\)记录了各个排名的LMS子串的起始位置。

IS(pos);

现在我们进行离散化,从小到大枚举每个LMS子串的起始位置,注意到可能和该LMS子串相等的只有前一个LMS子串,所以我们记录下前一个LMS子串的起始位置。
先判断该LMS子串和前一个LMS子串的长度关系,如果长度不等那就一定不相等。(实际上这只是一个效果非常好的常数优化)
否则我们暴力判断两个LMS子串是否相等,注意如果中间某个位置的后缀类型不相等也认为这两个LMS子串不相等。
由结论4我们知道LMS字串的长度总和不会超过\(n\),所以这里暴力判断的复杂度是\(O(n)\)的。


for(int i=1,x,y=0;i<=n;++i)
if(x=rank[sa[i]])
{
	if(M<=1||pos[x+1]-pos[x]!=pos[y+1]-pos[y]) ++M;
	else for(int a=pos[x],b=pos[y];a<=pos[x+1];++a,++b) if((s[a]<<1|t[a])^(s[b]<<1|t[b])) {++M;break;}
	S[y=x]=M;
}

此时我们就得到了新串,递归求其SA,用\(S\)代替\(pos\)临时记录各个排名对应的LMS后缀的起始位置。(如果\(N=M\)那么直接基数排序求SA)

if(M^N) SAIS(N,M,S,t+n,pos+n); else for(int i=1;i<=N;++i) sa[S[i]]=i;
for(int i=1;i<=N;++i) S[i]=pos[sa[i]];

最后再调用诱导排序求出原串的SA。

IS(S);

IS

刚才的部分已经非常清晰了,但是我们怎样诱导排序。
第一次是已知按下标顺序存放的所有LMS后缀的起始位置(\(pos\)),要求所有LMS子串的排名(只保证\(\operatorname{suf}_i\)为LMS后缀的\(i\)位置之间的排名的相对大小符合以其为首的LMS子串的相对大小的\(sa\))。
第二次是已知按LMS后缀字典序存放的所有LMS后缀的起始位置(\(S\)),要求所有\(\operatorname{suf}\)的排名(\(sa\))。
我们先考虑第二次诱导排序。
is是一个为了方便简写的函数,然后为了减少调用我们用宏写IS。



#define is(x,a) sa[r[s[x]]a]=x
#define IS(S)

先给原串基数排序处理出每个首字母开头的串在\(sa\)中对应的区间,倒序枚举LMS后缀并把它们插入\(sa\)中对应段的末尾。
(这里倒序枚举是为了保证\(sa\)中LMS后缀的相对排名是正确的,从而在下一部分能够以正确的顺序枚举L型后缀)

memset(sa+1,0,n<<2),memset(c+1,0,m<<2),for_each(s+1,s+n+1,[](int x){++c[x];}),partial_sum(c+1,c+m+1,c+1),memcpy(r+1,c+1,m<<2);
for(int i=N;i;--i) is(S[i],--);

然后我们需要把每个LMS后缀前面的一段L型后缀归并进来。
因为首字母相同的L型后缀都比S型后缀(包括LMS后缀)小,所以它们肯定是占据了\(sa\)中对应区间的一段前缀。
具体我们可以这样操作:从前往后扫\(sa\),假设当前的\(sa_i=k\),若\(k\ne1\)\(\operatorname{suf}_{k-1}\)是L型后缀,那么我们就把它插到当前\(sa\)中对应区间的最左边。
注意到我们实质上是从小到大枚举\(\operatorname{suf}\),而首字母相同的\(\operatorname{suf}_i,\operatorname{suf}_j\)的大小关系完全等同于\(\operatorname{suf}_{i+1},\operatorname{suf}_{j+1}\),因此以同一首字母开头的L型后缀也会从小到大被枚举到。
(这里就很好地解释了上面为什么要倒序枚举LMS后缀)
并且因为这是我们归并进来的都是L型后缀,都满足\(\operatorname{suf}_i>\operatorname{suf}_{i+1}\),所以在\(sa\)\(\operatorname{suf}_i\)插入的位置一定在\(\operatorname{suf}_{i+1}\)后面,所以不用担心数漏。




transform(c,c+m,r+1,[](int x){return x+1;});
for(int i=1;i<=n;++i) if(sa[i]>1&&t[sa[i]-1]) is(sa[i]-1,++);

然后再把S型后缀按照和上面完全一样的办法归并进来。
从后往前扫\(sa\),假设当前的\(sa_i=k\),若\(k\ne1\)\(\operatorname{suf}_{k-1}\)是S型后缀,那么我们就把它插到当前\(sa\)\(\operatorname{suf}_{k-1}\)对应区间的最右边。
具体的正确性证明参考L型后缀的部分。
注意到我们一开始LMS后缀插的位置并不正确,所以此时要重新排序。
(LMS后缀自身也是S型后缀,所以会在此时被排序,因此一开始放在后面就能不影响L型后缀的排序)



memcpy(r+1,c+1,m<<2);
for(int i=n;i;--i) if(sa[i]>1&&!t[sa[i]-1]) is(sa[i]-1,--);

现在我们已经完成了第二次诱导排序,接下来考虑第一次诱导排序。
第一次诱导排序是已知按下标顺序排列的所有LMS子串的初始位置,要求LMS子串的相对大小关系。
我现在告诉你只要IS(pos)就好了,没有任何其它的问题。
我们再观察一遍第二次诱导排序的过程,大概的流程是:倒序插入LMS后缀,给L型后缀排序,给S型后缀排序。
因为我们插LMS后缀的顺序可能不对,所以L型后缀可能不能正确地排序。
但如果我们把插入的东西看成LMS前缀的话,那么就是在从大到小插入LMS前缀(此时都只有一个字符)。
然后对于后面的步骤,可以用和上面类似的方法证明我们是在给LMS前缀排序。
那么我们就可以根据LMS前缀的排名来计算LMS子串的排名了。
但是实际上有更简便的途径:LMS子串的初始位置对应的LMS前缀都是按LMS子串的大小排好的。
证明:
对于首字母不相同的LMS子串显然成立。
对于首字母不同的LMS子串对应的LMS前缀,它们都是由一个左边的一个S型后缀对应的LMS前缀转移过来的,再依次类推可以得到它们都是有右边的第一个L型后缀对应的LMS前缀转移过来的,其实这个2过程就是比较了各个LMS字串的大小。因此命题成立。










Tips:

注意\(sa\)的第一个是$,所以要整体前移一位。\(rank\)的话直接由\(sa\)推就好了。

Code

#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
#include<numeric>
using std::partial_sum;
using std::transform;
using std::for_each;
namespace IO
{
    char obuf[(1<<21)+1],st[11],*oS=obuf,*oT=obuf+(1<<21);
    void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
    void Put(char x){*oS++=x;if(oS==oT)Flush();}
    void write(int x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put(' ');}
}using namespace IO;
const int N=1000007;
char str[N+10];int sa[N],rank[N],h[N],s[N<<1],t[N<<1],pos[N<<1],r[N>>1],c[N>>1];
#define is(x,a) sa[r[s[x]]a]=x
#define IS(S)\
    memset(sa+1,0,n<<2),memset(c+1,0,m<<2),for_each(s+1,s+n+1,[](int x){++c[x];}),partial_sum(c+1,c+m+1,c+1),memcpy(r+1,c+1,m<<2);\
    for(int i=N;i;--i) is(S[i],--);\
    transform(c,c+m,r+1,[](int x){return x+1;});\
    for(int i=1;i<=n;++i) if(sa[i]>1&&t[sa[i]-1]) is(sa[i]-1,++);\
    memcpy(r+1,c+1,m<<2);\
    for(int i=n;i;--i) if(sa[i]>1&&!t[sa[i]-1]) is(sa[i]-1,--);
void SAIS(int n,int m,int*s,int*t,int*pos)
{
    int N=0,M=rank[1]=0,*S=s+n;
    t[n]=0;
    for(int i=n-1;i;--i) t[i]=s[i]^s[i+1]? s[i]>s[i+1]:t[i+1];
    for(int i=2;i<=n;++i) rank[i]=t[i-1]&&!t[i]? pos[++N]=i,N:0;
    IS(pos);
    for(int i=1,x,y=0;i<=n;++i)
	if((x=rank[sa[i]]))
	{
	    if(M<=1||pos[x+1]-pos[x]!=pos[y+1]-pos[y]) ++M;
	    else for(int a=pos[x],b=pos[y];a<=pos[x+1];++a,++b) if((s[a]<<1|t[a])^(s[b]<<1|t[b])) {++M;break;}
	    S[y=x]=M;
	}
    if(M^N) SAIS(N,M,S,t+n,pos+n); else for(int i=1;i<=N;++i) sa[S[i]]=i;
    for(int i=1;i<=N;++i) S[i]=pos[sa[i]];
    IS(S);
}
int main()
{
    int n;
    fread(str+1,1,1000000,stdin),n=strlen(str+1);
    while(!isalpha(str[n])) --n;
    transform(str+1,str+n+1,s+1,[](char c){return c-'a'+2;}),s[++n]=1,SAIS(n--,27,s,t,pos);
    for(int i=1;i<=n;++i) rank[sa[i]=sa[i+1]]=i;
    for(int i=1,j,l=0;i<=n;h[rank[i++]]=l) for(j=sa[~-rank[i]],l-=l>0;i+l<=n&&j+l<=n&&s[i+l]==s[j+l];++l);
    for_each(sa+1,sa+n+1,[](int x){write(x);}),Put('\n'),for_each(h+2,h+n+1,[](int x){write(x);}),Flush();
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部