望月Asta
2022-01-14 13:24:30
参考 : 2021 年信息学奥林匹克中国国家集训队论文 代晨昕 后缀树的构建
似乎后缀树可以在一些题目代替 SAM 套 LCT 啊.
妈妈再也不怕我考场写不出LCT了
后缀树也写不出啊.
反正能写进国集论文的东西一定不会差(?)
从前向后构建后缀树的在线算法 Ukkonen 算法可视化
首先直接非常
时空复杂度
于是先看一下后缀 Tire 有什么不合理的地方 :
太多的结点前的转移仅仅是一条链,浪费大量空间.
考虑把 拥有多于一个儿子的结点 和 叶子结点 作为关键点.
建立只保留关键点和后缀,将非关键点压缩为一条边的 Trie 称作 后缀树.
建立只保留关键点的经过信息压缩的 Trie 称为 隐式后缀树.
举个例子,对于 cabab
建立上述三者 :
(图片来自 代晨昕论文,三者分别为 后缀 Trie,后缀树,隐式后缀树)
可以发现后缀树比隐式后缀树多了两个点,因为那两个点在隐式后缀树的关键点定义下不算关键点,但是是一个后缀结点,于是在后缀树中可以单独出现.
众所周知对于反串建 SAM 建出的 parent 树就是这个串的后缀树,那么我们得到了一个线性建立后缀树的在线方法,甚至支持前端添加字符.
Code :
倒着调用 extend()
即可.
struct SuffixAutomaton {
int tot,lst;
int siz[N << 1];
int buc[N],id[N << 1];
struct Node {
int len,link;
int ch[26];
}st[N << 1];
SuffixAutomaton() : tot(1),lst(1) {}
inline void extend(int ch) {
int cur = ++tot,p = lst;lst = cur;
siz[cur] = 1,st[cur].len = st[p].len + 1;
for(;p && !st[p].ch[ch];p = st[p].link)
st[p].ch[ch] = cur;
if(!p) st[cur].link = 1;
else {
int q = st[p].ch[ch];
if(st[q].len == st[p].len + 1)
st[cur].link = q;
else {
int pp = ++tot;st[pp] = st[q];
st[pp].len = st[p].len + 1;
st[cur].link = st[q].link = pp;
for(;p && st[p].ch[ch] == q;p = st[p].link)
st[p].ch[ch] = pp;
}
}
}
}SAM;
Ukkonen 算法是能够在线性时间构造一个字符串的 隐式后缀树 的在线算法.
通过上面的图和隐式后缀树的定义我们能够知道隐式后缀树的每个结点都对应原串
将
Lemma : 有
s 的隐式后缀s[i,n] ,那么\forall j > i,s[j,n] 是s 的隐式后缀.证明 :
s[i,n] 为隐式后缀,说明其原本的后缀结点不是叶子结点,即存在一个字符c \in \Sigma 使得s[i,n] + c 是s 的子串.而因为
s[j,n] 是s[i,n] 的子串,s[j,n] + c 一定也在s 中作为子串出现,s[j,n] 的后缀结点不是叶子结点,其在隐式后缀树上是不出现的.
于是可以发现隐式后缀是那些被包含了的短后缀.
考虑在结尾添加字符会影响什么.
在后缀 Trie 上新增结点,这是显然的.
隐式后缀树上,这只导致显式后缀父边增长,而主要影响的是隐式后缀.
现在我们维护一个重要的三元组
和 SAM 的后缀链接意思差不多.
Lemma : 对于隐式后缀树的一个非根非叶结点
x ,总有一结点y 使得c + mx_y = mx_x ,其中c 是一个字符.证明 : 首先
x 能在隐式后缀树出现,则必定有mx_x + c_1 和mx_x + c_2\ (c_1,c_2 \in \Sigma) 这两个串是s 的子串使得x 作为一个分歧点.于是
mx_y 也有mx_y + c_1 和mx_y + c_2 ,可知mx_y 是显然存在切作为独立结点的.
现在就将上面这个引理中所描述的