题解 P5353 【树上后缀排序】
xtx1092515503
2020-11-04 15:36:19
通过本题，我对后缀数组的理解又深了许多。
首先这是我普通SA的代码：
```cpp
namespace Suffix_Array{
const int N=1010000;
int x[N],y[N],sa[N],buc[N],n,m,s[N];
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num>=n)break;
m=num;
}
}
}
```
说一下各数组的含义：
$x$：前一次排序后的 $rk$ 数组，即位置 $i$ 的排名（对于相同的字符串，此值也相同）
$sa$：前一次排序后的 $sa$ 数组，即排名为 $i$ 的位置。
$y$：按照第二关键字（后半段字符串）的值排序后的结果
$buc$：桶。
------------
现在我们要把它转到树上，有什么变化呢？
首先，它对于相同的串的比较方式我们先不管，就假设所有串均不同。
然后，在序列上我们倍增可以直接跳下标，在树上倍增就必须依照树上倍增的 $anc$ 数组了。
------------
我们将上述代码截成四段，分别是预处理初始排序结果、按照第二关键字排序、按照第一关键字排序，以及由排序结果（$sa$ 数组）推出 $x$。
明显初始排序同序列排序并无区别。
按照第二关键字（后半段串）排序的部分：
1. 如果一个节点不存在 $k$ 级祖先，显然它第二关键字排序的结果应该在最前面。
2. 如果一个节点存在 $k$ 级祖先，因为两个节点可能有相同的 $k$ 级祖先，所以这部分仍需要排序一下，按照祖先的 $x$ 排序。
所以就能魔改成这样：
```cpp
int num=0;
for(int i=1;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)if(!anc[i][k])y[++num]=i;else ++buc[x[anc[i][k]]];
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)if(anc[i][k])y[num+buc[x[anc[i][k]]]--]=i;
```
按照第一关键字排序并无区别。
推 $x$ 的过程中，唯一区别即在于判断是否相等的 $mat$ 函数。此部分稍稍魔改一下就可以了：
```cpp
bool mat(int i,int j,int k){
if(y[i]!=y[j])return false;
if(!anc[i][k]&&!anc[j][k])return true;
if(anc[i][k]&&anc[j][k])return y[anc[i][k]]==y[anc[j][k]];
return false;
}
```
------------
下面我们回到原题——可能有相同的串。怎么办呢？
我们之前特意提到了，**对于相同的串，它们 $x$ 的值相同**。然后题面中的比较方式，实际上就是按照优先遍历小编号节点的dfs序进行排序。于是我们以最后一遍排序后的 $x$ 为第一关键字，dfs序为第二关键字，进行排序，即得到了最终结果。
此部分及主函数代码：
```cpp
int tot,dfn[500100];
vector<int>v[500100];
void dfs(int x){
dfn[x]=++tot;
sort(v[x].begin(),v[x].end());
for(auto y:v[x])dfs(y);
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++)scanf("%d",&anc[i][0]),v[anc[i][0]].push_back(i);
for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];
scanf("%s",s+1);for(int i=1;i<=n;i++)s[i]=s[i]-'a'+1;
SA();
dfs(1);
for(int i=1;i<=n;i++)sa[i]=i;
sort(sa+1,sa+n+1,[](int u,int v){return x[u]==x[v]?dfn[u]<dfn[v]:x[u]<x[v];});
for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",sa[i]);
// for(int i=1;i<=n;i++)printf("%d ",x[i]);
return 0;
}
```
AC代码就把前面几块代码拼一起即可。