后缀数组(SA)

字符串

作业部落

评论地址

---

一、概述

一个可以对一个字符串的所有后缀处理的算法
网上优秀博客

二、题单

• [luogu3809]【模板】后缀排序 https://www.luogu.org/problemnew/show/P3809
• [hihocoder1403] 后缀数组一·重复旋律 http://hihocoder.com/problemset/problem/1403
• [hihocoder1407] 后缀数组二·重复旋律2 http://hihocoder.com/problemset/problem/1407
• [hihocoder1415] 后缀数组三·重复旋律3 http://hihocoder.com/problemset/problem/1415
• [hihocoder1419] 后缀数组四·重复旋律4 http://hihocoder.com/problemset/problem/1419
• [POJ2774]Long Long Message https://vjudge.net/problem/POJ-2774
• [BZOJ4199][NOI2015]品酒大会 https://www.luogu.org/problemnew/show/P2178
• [BZOJ3238][AHOI2013]差异 https://www.luogu.org/problemnew/show/P4248
• [BZOJ3879]SvT https://www.lydsy.com/JudgeOnline/problem.php?id=3879
• [Luogu3538][POI2012]OKR-A Horrible Poem
• [BZOJ4892][TJOI2017]DNA https://www.luogu.org/problemnew/show/P3763
• [Luogu2852][USACO06DEC]牛奶模式Milk Patterns https://www.luogu.org/problemnew/show/P2852
• [Luogu2463][SDOI2008]Sandy的卡片 https://www.luogu.org/problemnew/show/P2463
• [BZOJ4566][HAOI2016]找相同字符 https://www.luogu.org/problemnew/show/P3181
• [BZOJ4556][TJOI2016&&HEOI2016]字符串 https://www.luogu.org/problemnew/show/P4094
• [BZOJ1031]字符加密 https://www.luogu.org/problemnew/show/P4051
• [luogu1368][BZOJ2882]工艺 https://www.luogu.org/problemnew/show/P1368
• [BZOJ4650][NOI2016]优秀的拆分
• [SPOJ] Distinct Substrings/New Distinct Substrings
• [BZOJ2946]公共串 http://172.40.25.127:5283/problem/112946
• [POJ1743]Musical Theme
• [luogu4143]采集矿石 https://www.luogu.org/problemnew/show/P4143

三、题解

[luogu3809]【模板】后缀排序
板子，求$SA$数组

[hihocoder1403] 后缀数组一·重复旋律
求$height$后单调队列求解至少出现$k$次的最长子串

[hihocoder1407] 后缀数组二·重复旋律2
[hihocoder1415] 后缀数组三·重复旋律3
[POJ2774]Long Long Message
[Luogu2852][USACO06DEC]牛奶模式Milk Patterns
求两个字符串中的最长公共子串，把两串中间用一个从未出现过的字符连起来，跑$SA$后二分答案，如果有互不重叠且$height$之$min$大于$mid$的那么返回$1$

[BZOJ3238][AHOI2013]差异Hard
求串$s$中任意两个子串的$lcp$(最长公共前缀)，利用性质$i$,$j$的$lcp$为$min(height[i+1]...height[j])$，所以维护一个单调递增栈，设$f[i]$表示栈中第$i$个位置到$1..i-1$个位置的所有贡献，通过$f[i]=height[i]*(i-sta[top])+f[sta[top]];$可以$O(1)$算贡献

[Luogu2463][SDOI2008]Sandy的卡片
[BZOJ2946]公共串
求多串中的最长公共子串，将所有串连接成一个串$s$，中间用一个从未出现过的字符隔开，那么$Get\_SA$后二分最长公共子串的长度，若$height$数组中有连续的一段$\ge mid$，且这一段中所有的子串都出现过，那么合法

• [BZOJ4566][HAOI2016]找相同字符 https://www.luogu.org/problemnew/show/P3181

[BZOJ1031]字符加密
把字符串$×2$，在按照$rank$数组输出符合条件的字符

• [hihocoder1419] 后缀数组四·重复旋律4 http://hihocoder.com/problemset/problem/1419

[BZOJ4199][NOI2015]品酒大会Hard
求最长公共前缀长度为$l$的后缀对数以及得分最大的一对的得分。
那么一段区间都大于等于$l$，它会被$0...l-1$都计算贡献，所以大的贡献不会影响小的贡献，把height排序之后从大到小处理，每处理一个$height[k]$就把$SA[k],SA[k-1]$两个串并起来，表示之后会一起处理，同时答案加上两个并查集的$siz$之积（两并查集内任意一对都符合条件），最大值便是两并查集最大值之积或最小值之积（负数）

[BZOJ4556][TJOI2016&&HEOI2016]字符串Hard
$O(logn)$求一个串$s_{c..d}$与一段区间$[a,b]$内的串的最长前缀。
二分答案，那么符合答案的是$SA$上一段连续的区间，分别二分左右端点，现在就是判断$SA$的$[l,r]$上是否存在一个数在$[a,b]$之间，转化为二维数点问题，用主席树完成

• [BZOJ3879]SvT https://www.lydsy.com/JudgeOnline/problem.php?id=3879
• [Luogu3538][POI2012]OKR-A Horrible Poem
• [BZOJ4892][TJOI2017]DNA https://www.luogu.org/problemnew/show/P3763
• [luogu1368][BZOJ2882]工艺 https://www.luogu.org/problemnew/show/P1368
• [BZOJ4650][NOI2016]优秀的拆分
• [SPOJ] Distinct Substrings/New Distinct Substrings
• [POJ1743]Musical Theme

[luogu4143]采集矿石Hard
得到函数单调的性质后，考虑用后缀数组求一个子串的排名
其实一个后缀$i$贡献的本质不同的字符串就是$len-Rank[i]+1-height[i]$
1如果$r-l+1>height[Rank[l]]$

$$Rank_{s_{l..r}}=(\sum_{i=1}^{Rank[L]-1}{len-Rank[i]+1-height[i]})+r-l+1-height[Rank[l]]$$ 2其他情况找到一个最大的$p$使得$r-l+1>lcp(l,p)$那么套用上式
然后这题枚举$l$二分下$r$，判断$Rank_{s_{l..r}}$与其权值是否相等即可

四、经验

$A.$
多个字符不好处理的时候在中间依次添加从未出现过的字符（第一次加$\#$第二次加$\&$什么的），使得前后两个字符不会有$height$的贡献

$B.$
排好序后，二分一段区间使得以区间任意一个位置为开头的字符串与字符串$x$($x$也在区间内)的最长前缀时，建议分别二分左右端点，而不是倍增地跳（调试2hTJOI2016字符串，因为不好选取倍增起点，ST表中任意一个数值都至少由两个字符串得来）

五、模板

洛谷3809后缀排序
记忆方式
Sort里面4行，预处理1行，倍增求SA枚举1行，中间5行
求height2行枚举3行内容

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=2200000;
char ch[MAXN];//字符串
int m=1000;//字符集大小
int s[MAXN],l,len1,len2;//字符串长度
int SA[MAXN];//SA[i]表示排名为i的字符串是以SA[i]为开头的后缀
int x[MAXN],y[MAXN];//记录两维信息方便排序
int t[MAXN];//桶
int Rank[MAXN];
int height[MAXN];
/*
  SA[i]=k 表示排名为i的是第k号串
  x[i]=k 表示i号串的第一关键字排名为k
  y[i]=k 表示第二关键字排名为i的是第k号串
  t[i]=k (统计前缀和之前)表示排名并列为i的串的数量是k
         (统计前缀和之后)表示排名为1～i的串的数量是k
  Rank[i]=k 表示第i号串的排名是k（与SA互逆）
  height[i]=k 表示lcp(Suffix(SA[i-1]),Suffix(SA[i]))
              就是排名为i-1的串和排名为i的串的最长公共前缀
 */
int cmp(int i,int j,int k)
{
    return y[i]==y[j]&&y[i+k]==y[j+k];
}
void Sort()
{
    for(int i=1;i<=m;i++) t[i]=0;
    for(int i=1;i<=l;i++) t[x[i]]++;
    for(int i=1;i<=m;i++) t[i]+=t[i-1];
    for(int i=l;i>=1;i--) SA[t[x[y[i]]]--]=y[i];//容易打反
}
void Get_SA()
{
    for(int i=1;i<=l;i++) x[i]=s[i],y[i]=i; Sort();
    for(int k=1,p=0;k<=l;k<<=1)
    {
        for(int i=l-k+1;i<=l;i++) y[++p]=i;
        for(int i=1;i<=l;i++) if(SA[i]>k) y[++p]=SA[i]-k;
        Sort();swap(x,y);x[SA[1]]=p=1;
        for(int i=2;i<=l;i++) x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;//容易x中不写SA[i]
        if(p==l) break; m=p;p=0;
        //如果第一维已经有序，那么就不需要继续排序了～
    }
    /*
    for(int i=1;i<=l;i++) Rank[SA[i]]=i;
    for(int i=1,j=0;i<=l;i++)
    {
        if(j) j--; //利用性质：height[Rank[i]]>=height[Rank[i-1]]-1
        while(s[i+j]==s[SA[Rank[i]-1]+j]) j++;
        height[Rank[i]]=j;
    }
     */
}
int main()
{
    scanf("%s",ch); int len=strlen(ch);
    for(int i=0;i<len;i++) s[++l]=ch[i];
    Get_SA();
    for(int i=1;i<=l;i++) printf("%d ",SA[i]);
    puts("");return 0;
}