SA-IS
缪凌锴_Mathew · · 算法·理论
前置
记
为方便,在
由于要往最后加
SL 型后缀
对于后缀
-
- $s_i<s_{i+1} -
-
- $s_i>s_{i+1} -
特别地,
相同首字符性质
性质:对于后缀
精炼版:首字符相同的后缀,必定有
证明:
-
s_x\ne s_{x+1}\land s_y\ne s_{y+1}\rArr s_{x+1}>s_x=s_y>s_{y+1} -
s_x\ne s_{x+1}\land s_y=s_{y+1}\rArr s_{x+1}>s_x=s_y=s_{y+1} -
s_x=s_{x+1}\land s_y\ne s_{y+1}\rArr s_{x+1}=s_x=s_y>s_{y+1} -
s_x=s_{x+1}\land s_y=s_{y+1}$,递归比较 $\suf_{x+1},\suf_{y+1}
LMS 位置 & 子串
位置
即每个
用后缀大小关系来看,LMS 位置
显然
将 LMS 后缀
相邻两个 LMS 位置
LMS 子串的类型形如:
相邻两个 LMS 子串首尾共用一个 LMS 位置。
重要引理
引理:
不存在两个 LMS 子串
X,Y 满足:
子串
证明:满足条件的
LMS 后缀排序引理
考虑将所有 LMS 子串排序,得到一个 LMS 子串的
引理:
将所有 LMS 位置的后缀排序,对于两个后缀
\suf_x,\suf_y :从
x 开始有若干个 LMS 子串,记序列X 为这些 LMS 子串的rnk 值。同理
y 开始的 LMS 子串求出序列Y 。必定有:
\suf_x,\suf_y 的字典序关系等于X,Y 的字典序关系。
举个例子:
-
$x,y$ 肯定不是同一个 $\P$ 诱导的,因为同一个 $\P$ 左侧的那段 $\L$ 字符单调不升。 因此 $y+1$ 到它的 $\P$ 这段字符都比 $s_{x+1}$ 小,这条诱导链肯定可以在扫到 $x+1$ 之前完成。 于是扫到 $x+1$ 诱导出 $x$ 之前,一定会扫到 $y+1$,$y$ 就会被诱导了。 $y$ 比 $x$ 先被诱导,即入桶,矛盾。 -
LMS 子串排序
现在问题只剩求
结论:将
只观察最后一个字符,即一开始的按首字母排序,结果是对的。
同上面诱导排序证明,只观察 LMS 子串,求出的 sa 是对的。
实现
inline void SAIS(int*s,int*sa,int n,int sig){
char t[n+2];
memset(t,'\0',sizeof(char)*(n+2));
t[n]='S';
for(int i=n-1;i;i--)
{
t[i]=s[i]==s[i+1]?t[i+1]:(s[i]<s[i+1]?'S':'L');
}
static bool lms[MAXN];
for(int i=2;i<n;i++)
{
lms[i]=t[i]=='S'&&t[i-1]=='L';
}
lms[n]=true;
int c=0;
int p[n/2+2];
p[0]=0;
for(int i=1;i<n;i++)
{
if(lms[i]){
p[++c]=i;
}
}
p[++c]=n;
static int sum[MAXN];
memset(sum,0,sizeof(int)*(sig+1));
for(int i=1;i<=c;i++)
{
sum[s[p[i]]]++;
}
for(int i=1;i<=sig;i++)
{
sum[i]+=sum[i-1];
}
int rnk[n+1];
rnk[0]=0;
for(int i=1;i<=c;i++)
{
rnk[i]=sum[s[p[i]]]--;
sa[rnk[i]]=i;
}
auto IS=[&](){
static int L[MAXN],S[MAXN];
memset(sum,0,sizeof(int)*(sig+1));
for(int i=1;i<=n;i++)
{
sum[s[i]]++;
}
for(int i=1;i<=sig;i++)
{
sum[i]+=sum[i-1];
L[i]=sum[i-1]+1;
S[i]=sum[i];
}
int sa_[c+1];
memcpy(sa_,sa,sizeof(int)*(c+1));
memset(sa,0,sizeof(int)*(n+1));
for(int i=c;i;i--)
{
sa[S[s[p[sa_[i]]]]--]=p[sa_[i]];
}
for(int i=1;i<=n;i++)
{
if(sa[i]>1&&t[sa[i]-1]=='L'){
sa[L[s[sa[i]-1]]++]=sa[i]-1;
}
}
for(int i=c;i;i--)
{
sa[++S[s[p[sa_[i]]]]]=0;
}
sa[S[s[p[c]]]--]=p[c];
for(int i=n;i;i--)
{
if(sa[i]&&t[sa[i]-1]=='S'){
sa[S[s[sa[i]-1]]--]=sa[i]-1;
}
}
};
IS();
int k=0;
for(int i=1,j=0;i<=n;i++)
{
auto chk=[&](int x,int y){
if(s[x]^s[y]){
return false;
}
x++;
y++;
while(!lms[x]||!lms[y])
{
if(lms[x]||lms[y]||s[x]^s[y]){
return false;
}
x++;
y++;
}
return true;
};
if(lms[sa[i]]){
int x=sa[i];
k++;
if(j&&chk(j,x)){
k--;
}
j=x;
rnk[x]=k;
}
}
for(int i=1;i<=c;i++)
{
rnk[i]=rnk[p[i]];
}
if(k==c){
for(int i=1;i<=c;i++)
{
sa[rnk[i]]=i;
}
}
else{
SAIS(rnk,sa,c,k);
}
IS();
}
inline void SA(){
static int S[MAXN];
for(int i=1;i<=n;i++)
{
S[i]=s[i];
}
S[n+1]=1;
S[n+2]=128;
SAIS(S,sa,n+2,128);
for(int i=1;i<=n;i++)
{
sa[i]=sa[i+1];
}
}
OI-Wiki 上有个卡空间到极致的做法:最优原地后缀排序算法
效率
时间复杂度
但是 IS 虽然是线性但是非常慢,实测
但总体来说高贵的线性还是会比极限卡常的单
QOJ 板题:单
参考文献
- 再谈后缀数组:SA-IS
- 诱导排序与 SA-IS 算法