Trie上的后缀数组

亦称为广义后缀数组

Definition

LCS=Longest Common Suffix
LCP=Longest Common Preffix
Sv$S_v$表示Trie上节点v到根的路径形成的字符串

Intro

由于在Trie上，自带去重功能
显然LCS(Su,Sv)=deplca(u,v)$LCS(S_u,S_v)=de{p}_{lca(u,v)}$
我们要实现后缀数组的功能，即把sa,rank,H(height)$sa,rank,H(height)$都求出来
sa,rank$sa,rank$很好求，类比序列情形，倍增，将两个长度2i−1$2^{i-1}$的信息双关键字排序得到2i$2^i$长度的信息。这里，我们只需取出每个点的2i−1$2^{i-1}$级祖先。
其余部分类似于序列上的做法。
然后我们要兹磁查询LCP(Su,Sv)$LCP(S_u,S_v)$
一个思路是求出Hi$H_i$，即LCP(Ssai−1,Ssai)$LCP(S_{s{a}_{i-1}},S_{s{a}_i})$
一个方法是二分+哈希，但是有更简单的做法，我们对倍增过程每个点的rank$rank$保留下来（据说这叫波兰表），那么我们可以倍增求任意两个点的LCP$LCP$，代码大概长这样

int LCP(int u , int v) {
    if (u == v)
        dep[u];
    int l = 0;
    per (i , lg , 0) if (rk[u][i] == rk[v][i]) {
        l += 1 << i;
        u = pa[u][i] , v = pa[v][i];
    }
    return l;
}

然后类似地，使用ST表支持RMQ即可O(1)询问任意两点LCP