后缀自动机 2019-05-03

一些后缀自动机的定义以及用法,备忘。本文又名:"\(\color{red}{\text{V}}\text{iXbob}\)手把手教你后缀自动机"

\(\text{Endpos}\)

记主串为\(\text{S}\), \(\text{T}\)\(\text{S}\)的一个子串。 \(\text{endpos(T)}\)表示\(\text{T}\)\(\text{S}\)中出现位置的结束位置的集合。

\(\text{State}\)

\(\text{p}\)\(\text{S}\)的后缀自动机的一个状态,同一个状态是\(\text{endpos}\)相同的\(\text{S}\)的子串的集合。

\(\text{S}\)为"aabbc",那么"bb","abb","aabb"的\(\text{endpos}\)都是{4},他们在后缀自动机上属于同一个状态。

\(\text{Trans}\)

\(\text{trans[p][c]}\)表示\(\text{p}\)所代表的字符串的集合中的[(加上\(\text{c}\)这个字符后仍是主串\(\text{S}\)的子串)的字符串构成的集合]所在的状态。

\(\text{S}\)为"abc",那么状态{"ab","b"}的转移边c所指向的状态为{"abc","bc","c"},并且空集的转移边c所指向的转态也是{"abc","bc","c"}。

\(\text{Parent Tree}\)

定义\(\text{Right(p)}\)表示\(\text{p}\)状态中的所有字符串的\(\text{endpos}\)集合(属于同一个状态的所有字符串的\(\text{endpos}\)集合都相等)。

\(\text{parent(p)}\)表示包含\(\text{Right(p)}\)\(\text{Right}\)集合大小最小的\(\text{Right}\)集合所对应的状态。

\(\text{Minlen and Maxlen}\)

\(\text{maxlen(p)}\)表示\(\text{p}\)这个状态中最长的字符串的长度,\(\text{minlen(p)}\)表示\(\text{p}\)这个状态中最短的字符串的长度。

性质:\(\text{minlen(p) = maxlen(parent(p))+1}\)

\(\text{Tricks}\)

\(\text{Parent Tree Multiplication}\)

可以在\(\text{O(logn)}\)的时间内确定\(\text{S}\)的一个子串在后缀自动机上所在的状态。

记子串为\(\text{[L…R]}\),答案一定为\(\text{[1..R]}\)所在的状态在\(\text{parent}\)树上的祖先。由于\(\text{minlen(p) = maxlen(parent(p))+1}\),只需要找到\(\text{maxlen}\)大于等于\(\text{R-L+1}\)的在\(\text{parent}\)树上深度最小的那个点就是答案。

\(\text{Segment Tree Merge On Parent Tree}\)

我们只需要从\(\text{Parent Tree}\)的叶子节点向上依次合并\(\text{Right}\)集合即可知道每个状态的\(\text{Right}\)集合信息。