跳转至

回文树

EERTREE,又称回文树(Palindrome tree)、回文自动机(PAM),是一种能在 \(O(\left|S\right|\log{\left|\Sigma\right|})\) 的时间与 \(O(\left|S\right|)\) 的空间内处理与 回文串 有关问题的数据结构。

Bonus

EERTREE 是一个 回文串,也许这就是这个数据结构的名字的来历。

回文树的高级应用慢慢写,持续更新。

pdf 论文

写在前面

为了更方便地描述字符串相关内容,我们做出以下规定:

  1. \(S, T\) 通常表示一个字符串,\(c\) 通常表示一个字符,\(\Sigma\) 表示字符集;
  2. \(\left|S\right|\) 表示字符串长度;
  3. \(\left|\Sigma\right|\) 表示字符集大小;
  4. \(S[l..r]\) 表示 \(S[l], S[l + 1], \ldots, S[r - 1], S[r]\)
  5. \(\epsilon\) 表示空串;
  6. \(S \subset T\) 表示 \(S\)\(T\) 的子串,即 \(\exists i \in [1, \left|T\right| - \left|S\right|], \text{s.t. } \forall j \in [1, \left|S\right|], S[j] = T[i + j - 1]\)
  7. \(\overleftarrow{S}\) 表示 \(S\) 的翻转,即 \(\forall i \in [1, \left|S\right|], \overleftarrow{S}[i] = S[\left|S\right|- i + 1]\)
  8. \(S\) 为回文串当且仅当 \(S = \overleftarrow{S}\),即 \(\forall i \in [1, \left|S\right|], S[i] = S[\left|S\right| - i + 1]\)
  9. \(S\) 为回文串,则定义 \(r(S)\) 为其最长回文半径,即 \(r(S) = \max\\{\left\lfloor\dfrac{\left|T\right| + 1}{2}\right\rfloor\\}, T \subset S, T = \overleftarrow{T}\)

特殊地,本文的字符串下标、回文树内节点编号 均从 \(1\) 开始

一些字符串有关术语的例子

对于 \(S = \mathtt{ABCBAD}\) 而言:

  1. \(\left|S\right| = 6\)
  2. \(\left|\Sigma\right| = 4\)
  3. \(S[2..4] = \mathtt{BCBA}\)
  4. \(S[1..4] \subset S[1..5]\)
  5. \(\overleftarrow{S[3..5]} = \mathtt{DAB}\)
  6. \(S[1..5] = \mathtt{ABCBA} = \overleftarrow{S[1..5]}\) 为回文串。

结构、操作与建立

为什么

我们考虑一个长度为 \(n\) 的回文串 \(S\),令 \(P = \{ T : T = S[i..n - i + 1] \quad i \in [1, \left\lfloor\dfrac{n + 1}{2}\right\rfloor]\}\),则 \(\forall x \in P, x = \overleftarrow{x}\)

那么 \(\forall x \in P\) 之间又有什么样的关系呢?

不难发现,一个回文串,是很多 子回文串层层嵌套 而成的。

也就是说,一个回文串,通过 在两端添加相同的字符,可以形成一个新的回文串。

至此,我们寻觅到了回文树上 边的意义

在回文树中,\(u\) 的父亲连向 \(u\) 的边上存储着字符 \(c\) 的意义是 \(u\) 的父亲表示的回文串,在两端加上 \(c\) 后,能形成 \(u\)

是什么

{% noteblock success %} 引理 1:向 \(S\) 末尾添加一个字符 \(c\) ,最多只会新生成一个回文子串。 {% endnoteblock %}

{% folding "证明" %} 这个子串是 \(S\)最长回文后缀 末端增加 \(c\),且原来的前端恰好也是 \(c\),所产生的。

也就是说,每次在 \(S\) 的末尾添加一个字符,最多只会新建一个节点。

$\blacksquare$

{% endfolding %}

回文树的内部结构,是一个包含着额外信息的有向图。

在后文中,我们可能会用回文子串来表示一个节点。

回文树支持两个操作:\(\text{add}(c)\)\(\text{eertree}(S)\)

  • \(\text{add}(c)\) 表示在回文树内插入 \(c\),返回此次操作新增的回文子串个数。

通过引理 1,我们可以知道 \(\text{add}(c)\) 总是返回 \(0\)\(1\)

不难发现,每次 \(\text{add}\) 操作之后,我们都能在 \(O(1)\) 的时间内得到已经处理了的字符串 \(T\) 的最长回文后缀,即 \(\text{maxSuf}(T)\)

  • \(\text{eertree}(S)\) 表示将 \(S\) 内的字符,从左至右逐个插入后形成的回文树。

{% noteblock warning %} 小结 1:\(S\) 中包含的本质不同的回文子串数量为 \(\text{eertree}(S)\) 的节点中的最大编号。 {% endnoteblock %}

一棵回文树上的每一个节点上要存储的信息有:

  1. 这个点的序号 \(u\)
  2. 表示的回文串的长度 \(len_u\)
  3. 从这个点出发的一条标为 \(c\) 的出边指向的节点的编号 \(ch_{u, c}\)
  4. 回文链接 \(fail_u\)

为了以后的方便,我们需要在初始化的时候新建两个节点,长度和编号分别为 \(-1\)\(0\)

\(0\) 表示着空串,称之为「偶根」;而 \(-1\) 表示着「虚串」,称之为「奇根」。

  • 偶根(即 \(0\))连出的边(如果存在),指向 \(cc\),表示在 \(\epsilon\) 的两侧同时添加 \(c\) 所形成的的字符串为 \(cc\)
  • 奇根(即 \(-1\))连出的边(如果存在),指向 \(c\),表示原来长度为 \(-1\) 的串,在两侧同时添加 \(c\) 形成了长度为 \(1\) 的字符串 \(c\)

节点 \(u\) 连至 \(v\) 的回文链接 \(fail_u\) 意味着 \(v\) 表示的回文串 \(S\)\(u\) 表示的回文串 \(T\) 的次长回文后缀子串(因为最长的是自己本身)。

我们 定义 \(fail_c = 0, fail_0 = fail_{-1} = -1\)

{% noteblock success %} 引理 2:任一满足 \(len_u > 0\) 的节点 \(u\) 的入度为 \(1\)(注意,这里的「入度」不将「回文链接」计算在内)。 {% endnoteblock %}

{% folding "证明" %} 1. 若 \(len_u = 1\),则其唯一的入边必为 \(-1 \to u\)

  1. \(len_u = 2\),则其唯一的入边必为 \(0 \to u\)

  2. \(len_u \ge 3\),则其唯一的入边必为 \(v \to u\),满足:\(v\) 表示的回文子串 \(T\) 的两端添加某个字符 \(c\) 能使得 \(u\) 表示的回文子串 \(S\) 满足 \(S = cTc\)

综上所述,任一满足 \(len_u > 0\) 的节点 \(u\) 的入度为 \(1\)

$\blacksquare$

{% endfolding %}

{% noteblock success %} 命题 1:建立一个长度为 \(n\) 的字符串 \(S\) 的回文树 \(\text{eertree}(S)\) 的空间复杂度为 \(O(n)\)。 {% endnoteblock %}

{% folding "证明" %} 由引理 1 可知,在 \(S\) 的逐步插入过程中,最多会新建 \(n\) 个节点;而还有 \(2\) 个初始化时新建的节点。

所以节点个数为最多为 \(n + 2\) 个。

由引理 2 可知,边的个数最多为 \(n\) 个;回文链接最多有 \(n\) 个。

综上所述,建立 \(\text{eertree}(S)\) 的空间复杂度为 \(O(n)\)

$\blacksquare$

{% endfolding %}

怎么做

\(S_0 = \mathtt{EERTREE}\) 为例,我们对它建立一棵回文树。

  1. 首先,我们先新建两个点,钦定它们为「奇根 \(1\)」和「偶根 \(0\)」。

一棵空的回文树是这样的(红色边为 \(fail\) 边,蓝色边为 \(ch\) 边,后同):

一棵空的 EERTREE

  1. 然后我们插入 \(\mathtt{E}\),现在 \(S = \mathtt{E}\)

插入 'E' 后的 EERTREE

  1. 接着我们插入 \(\mathtt{E}\),现在 \(S = \mathtt{EE}\)

插入 'EE' 后的 EERTREE

  1. 接着我们插入 \(\mathtt{R}\),现在 \(S = \mathtt{EER}\)

插入 'EER' 后的 EERTREE

  1. 接着我们插入 \(\mathtt{T}\),现在 \(S = \mathtt{EERT}\)

插入 'EERT' 后的 EERTREE

  1. 接着我们插入 \(\mathtt{R}\),现在 \(S = \mathtt{EERTR}\)

插入 'EERTR' 后的 EERTREE

  1. 接着我们插入 \(\mathtt{E}\),现在 \(S = \mathtt{EERTRE}\)

插入 'EERTRE' 后的 EERTREE

  1. 接着我们插入 \(\mathtt{E}\),现在 \(S = \mathtt{EERTREE}\)

插入 'EERTREE' 后的 EERTREE

我们应该如何实现这个过程呢?

{% noteblock success %} 命题 2:建立一个长度为 \(n\) 的字符串 \(S\) 的回文树 \(\text{eertree}(S)\) 的时间复杂度可达到在线 \(O(n\log\left|\Sigma\right|)\)。 {% endnoteblock %}

{% folding "证明" %} 在初始化的时候,我们得到了 \(\text{eertree}(\epsilon)\),即一个「奇根」和一个「偶根」加上它们的回文链接。

\(S\) 建造回文树的时候,我们会依次向回文树中插入 \(S[1], S[2], \ldots, S[n]\)

我们要使得在每次 \(\text{add}\) 操作之后,回文树中的所有节点之间的边以及回文链接都被正确维护。

考虑进行完了第 \(i\) 次操作后的状态,我们已经处理了 \(T = S[1..i]\) 的回文树,现在要插入 \(c = S[i + 1]\)


我们现在的目标是寻找 \(S[1..i + 1] = Tc\) 的最长回文后缀 \(P\)

显然,要么 \(P = c\),要么 \(P = cQc\)(显然 \(Q\)\(S[1..i]\) 的某一回文后缀)。

也就是说,我们需要找到 \(T\) 中,以 开头的前一位\(c\) 的最长回文后缀 \(Q\)

我们从 \(\text{maxSuf}(T)\) 开始,沿着回文链接遍历,设当前节点为 \(v\),比较 \(c\)\(T[i - len_v - 1]\)

怎么理解呢?\(T[i - len_v..i - 1]\) 是某一回文串 \(Q\),我们要找的,是满足 \(Q\) 开头的前一位为 \(c\) 的某一回文串。

也就是要保证 \(c = T[i - len_v - 1]\)

不难发现,特殊地,当 \(P = c\) 时,\(Q\) 对应的节点为「奇根」。


  1. \(P = c\)

检查 \(ch_{-1, c}\) 是否存在:

  1. 若不存在,则新建一个节点 \(v\),使 \(ch_{-1, c} = v, len_v = 1, fail_v = 0\)
  2. 若存在,根据定义,\(fail_v = 0\) 不需要更新。

  3. \(P = cQc\)

\(Q\) 对应的节点的序号为 \(u\)

检查 \(ch_{u, c}\) 是否存在:

  1. 若不存在,则新建一个节点 \(v\),使 \(len_v = len_u + 2\),连接 \(u \to v\),还要更新 \(fail_v\)

  2. 若存在,我们只需要考虑更新 \(fail_v\)

考虑 \(fail_v\) 到底会指向哪里?会指向 \(S[1, i] = Tc\) 的次长回文后缀。

\(cQc\)开头的前一位\(c\) 的次长回文后缀 \(R\)

若我们从 \(u\) 开始遍历回文链接,那么找到的会是 \(cQc\) 这个最长回文后缀;

因此我们应从 \(x = fail_u\) 开始遍历,仍然是比较 \(c\)\(T[i - len_x - 1]\)


接下来我们来分析 \(\text{add}\) 操作的时间复杂度。

  1. 我们每次检查 \(ch_{u, c}\)(或是检查 \(ch_{-1, c}\))是否存在,需要 \(O(\log\left|\Sigma\right|)\) 的时间复杂度(std::map 之类的数据结构实现)

实际情况下,我们使用子节点数组来实现,单次 \(\text{add}\) 的时间复杂度是 \(O(\left|\Sigma\right|)\) 的。

则一共 \(n\) 次,共 \(O(n \log\left|\Sigma\right|)\)

  1. 令已经处理了的字符串 \(S[1..i] = T\),考虑 \(\text{maxSuf}(T)\) 的末尾在 \(S\) 中的下标 \(j\) 的变化:

  2. 一个 \(fail\) 的转移会使 \(j\) 向左至少移动一格;

  3. 一个 \(ch\) 转移会使 \(j\) 向右至少移动一格。

在处理整个 \(S\) 的过程中,向左最多移动 \(n\) 格,也就是最多 \(n\) 次;向右最多移动 \(n\) 格,也就是最多 \(n\) 次。

因此转移部分的时间复杂度为总共 \(O(n)\)

总时间复杂度为 \(O(n) + O(n\log\left|\Sigma\right|) = O(n\log\left|\Sigma\right|)\)

综上所述,建立一个长度为 \(n\) 的字符串 \(S\) 的回文树 \(\text{eertree}(S)\) 的时间复杂度可达到在线 \(O(n\log\left|\Sigma\right|)\)

$\blacksquare$

{% endfolding %}

代码实现

后文有吧。

性质

我们称一个节点 \(u\) 是「奇」的,当且仅当 \(len_u\) 为奇数;称一个节点 \(v\) 是「偶」的,当且仅当 \(len_v\) 为偶数。

{% noteblock success %} 引理 3: 1. 一棵回文树本质上是两个弱连通图:以「奇根」和「奇点」构成的一个弱连通子图和以「偶根」和「偶点」构成的一个弱连通子图,且均为树。 2. 「奇点」和与其相连的边构成的树是 \(S\) 右半部分长度为奇数的回文子串构成的 trie;「偶点」和与其相连的边构成的树是 \(S\) 右半部分长度为偶数的回文子串构成的 trie。 3. 一棵回文树中的所有节点与连接在每个节点上的回文链接的反向链接构成一棵有向基环树,其中环为 \(-1\) 节点的自环。 {% endnoteblock %}

{% folding "证明" %} 1. 如果边 \(e = u \to v\) 存在,则 \(len_v = len_u + 2\),显然 \(u, v\) 奇偶性相同,则「奇点」与「偶点」之间互不相通。

结合引理 2,此性质得证。

  1. 这是回文树上边的定义和 trie 的定义。

  2. 注意到,除了 \(fail_{-1}\),其他的回文链接均会使 \(len\) 减小,且回文树中的每个点均有唯一的回文链接。

则每个点都仅有唯一简单路径到达 \(-1\),这显然是一棵(带有一个环)的树。

$\blacksquare$

{% endfolding %}

{% noteblock warning %} 小结 2:一些基本的字符串数据结构如回文 trie、后缀 trie 的空间复杂度都是 \(O(n^2)\) 的;像后缀树和 Compressed trie 这样很复杂的数据结构空间复杂度是 \(O(n)\) 的。但回文树这么简明易懂的数据结构的空间复杂度也是 \(O(n)\) 的。岂不妙哉? 更重要的是,一个字符串中本质不同的回文串期望个数\(O(\sqrt{\left|S\right|\cdot\left|\Sigma\right|})\) 的。也就是说,回文树的期望空间复杂度更佳。 {% endnoteblock %}

{% noteblock warning %} 小结 3:我们定义一个映射 \(\theta :\Sigma \to \Sigma, \text{s.t. } \theta^2(S) = S\)。我们称一个字符串 \(S\)\(\theta\)-回文的,当且仅当 \(S = \theta(\overleftarrow{S})\)。一个长度为 \(n\) 的字符串 \(S\)\(\theta\)-回文树仍可以在 \(O(\left|S\right|\log{\left|\Sigma\right|})\) 的时间与 \(O(\left|S\right|)\) 的空间内建立起来。 {% endnoteblock %}

基础应用

  1. 「APIO2014」回文串

题意:给定一个长度为 \(n\) 的字符串 \(S\),求 \(\max\\{\left|T\right|\cdot \text{occ}(S, T)\\}, T \subset S \land T = \overleftarrow{T}\)

其中 \(\text{occ}(S, T)\) 表示 \(T\)\(S\) 中的出现次数,\(1 \le \left|S\right| \le 3 \cdot 10^5\)

  1. 「MIPT Fall Programming Training Camp2014」B. Pairs

题意:给定一个长度为 \(n\),字符集为 \(\Sigma\) 的字符串 \(S\),求满足 \(1 \le i \le j < k \le n \land (S[i..j] = \overleftarrow{S[i..j]}) \land (S[j + 1..k] = \overleftarrow{S[j + 1..k]})\) 的三元组 \((i, j, k)\) 的个数。

\(1 \le n \le 3 \cdot 10^5\)

性质 3:「APIO2014」回文串 能用回文树在 额外 \(O(n)\) 的时间和空间 内解决。

{% folding "证明" %} 令 \(\text{occ}[u]\) 表示节点 \(u\) 对应的字符串 \(T\)\(S\) 中的出现次数。

\(\text{occAsMax}[u]\) 表示满足 \(\text{maxSuf}(S[1, i]) = T\)\(i\) 的个数,这个可以直接在每次 \(\text{add}\) 之后实时维护。

不难发现, $$ \text{occ}[u] = \text{occAsMax}[u] + \sum_{v:fail_v = u}\text{occ}[v] $$ 因为,\(T\)\(S\) 中出现,要么是以 \(T = \text{maxSuf}(S[1..i])\) 的形式出现,要么是以 \(T = \text{maxSuf}(S[l..r]), S[l..r] = \overleftarrow{S[l..r]}\) 的形式出现。

考虑到前者即 \(\text{occAsMax}[u]\),后者即满足 \(fail_v = u\)\(\text{occ}[v]\),则上述式子成立。

由引理 3 可知,我们可以自底向上地维护 \(\text{occ}[u]\)

maxNode 是最大节点编号)

1
2
3
4
for(int i = maxNode; i >= 1; --i)
    occ[i] = occAsMax[i];
for(int i = maxNode; i >= 1; --i)
    occ[ fail[i] ] += occ[i];

我们得到了 \(\text{occ}\) 之后,答案即为 \(\mathop{\operatorname{argmax}}\limits_{\text{occ}[u]}(\text{occ}[u]\cdot len_u)\)


不难发现,这额外维护的一部分时间复杂度和空间复杂度均为 \(O(n)\)


在实现的过程中,因为 C++ 不支持访问负数数组下标,所以我们 整体把下标加一,即 \(0\) 代表「奇根」,\(1\) 代表「偶根」……以此类推。

此时 maxNode 即为 cntNode - 1\(1\) 号节点的编号实际上为 \(2\)(处理 \(\text{occ}\) 的时候要注意)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define LL long long

const int N = 3e5 + 5;
const int C = 26 + 5;

int m;
char str[N];

struct EERTREE {
    static const int MS = N;
    int n, cntNode, last, s[MS], len[MS], ch[MS][C], fail[MS];
    int occAsMax[MS], occ[MS];

    int make(int ll) {
        len[cntNode] = ll;
        for(int i = 0; i < C; ++i)
            ch[cntNode][i] = 0;
        return cntNode++;
    }
    int getfail(int x) {
        while(s[n] != s[n - len[x] - 1])
            x = fail[x];
        return x;
    }
    bool add(int x) {
        s[++n] = x;
        int u = getfail(last), flg = 0;
        if(!u) {
            if(!ch[u][x]) {
                int v = make(1);
                ch[u][x] = v;
                fail[v] = 1;
                flg = 1;
            }
        }
        else {
            if(!ch[u][x]) {
                int v = make(len[u] + 2);
                ch[u][x] = v;
                flg = 1;
            }
            fail[ ch[u][x] ] = ch[getfail(fail[u])][x];
        }
        last = ch[u][x];
        ++occAsMax[last];
        return flg;
    }
    LL getocc() {
        LL ans = -1;
        // 这里要注意迭代的范围
        for(int i = cntNode - 1; i >= 2; --i)
            occ[i] = occAsMax[i];
        for(int i = cntNode - 1; i >= 2; --i)
            occ[ fail[i] ] += occ[i];
        for(int i = cntNode - 1; i >= 2; --i)
            ans = std::max(ans, 1LL * occ[i] * len[i]);
        return ans;
    }
    void init() {
        n = cntNode = last = 0;
        make(-1), make(0);
    }
} t;

int main() {
    scanf("%s", str + 1);
    m = strlen(str + 1);
    t.init();
    for(int i = 1; i <= m; ++i)
        t.add(str[i] - 'a' + 1);
    printf("%lld", t.getocc());
    return 0;
}

$\blacksquare$

{% endfolding %}

性质 4:「MIPT Fall Programming Training Camp2014」B. Pairs 能用回文树在 额外 \(O(n\log\left|\Sigma\right|)\) 的时间和 \(O(n)\) 的空间 内解决。

{% folding "证明" %} 首先,我们建立起 \(\text{eertree}(S)\)

我们用 \(\text{maxSuf}[i]\) 来表示 \(\text{maxSuf}(S[1..i])\),这个显然能在 \(O(n)\) 的空间内在每次 \(\text{add}\) 操作之后维护。

我们令 \(\text{sufCount}[u]\) 表示编号为 \(u\) 的节点对应的字符串的回文后缀的个数。

同理我们还要求出 \(\text{maxPre}\)\(\text{preCount}\)。注意到它们分别对应的是 \(\overleftarrow{S}\)\(\text{maxSuf}\)\(\text{sufCount}\)(记为 \(\text{maxSuf}'\)\(\text{sufCount}'\)。。

于是,我们建立起 \(\text{eertree}(\overleftarrow{S})\)

答案即为 $$ \sum_{i = 1}^{n - 1}\text{sufCount}[\text{maxSuf}[i]]\cdot\text{sufCount}'[\text{maxSuf}'[n - i]] $$


不难发现这部分的时间复杂度是 \(O(n\log\left|\Sigma\right|)\) 的,空间复杂度是 \(O(n)\) 的。

md 没得地方交这道题,代码仅供参考。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define LL long long

const int N = 3e5 + 5;
const int C = 26 + 5;

int m;
char str[N];
LL ans;

struct EERTREE {
    static const int MS = N;
    int n, cntNode, s[MS], len[MS], ch[MS][C], fail[MS];
    int sufCount[MS], maxSuf[MS];

    int make(int ll) {
        len[cntNode] = ll;
        for(int i = 0; i < C; ++i)
            ch[cntNode][i] = 0;
        return cntNode++;
    }
    int getfail(int x) {
        while(s[n] != s[n - len[x] - 1])
            x = fail[x];
        return x;
    }
    bool add(int x) {
        s[++n] = x;
        int u = getfail(maxSuf[n - 1]), flg = 0;
        if(!u) {
            if(!ch[u][x]) {
                int v = make(1);
                fail[v] = 1;
                ch[u][x] = v;
                flg = 1;
            }
        }
        else {
            if(!ch[u][x]) {
                int v = make(len[u] + 2);
                ch[u][x] = v;
                flg = 1;
            }
            fail[ ch[u][x] ] = ch[getfail(fail[u])][x];
        }
        sufCount[ch[u][x]] = sufCount[ fail[ch[u][x]] ] + 1;
        maxSuf[n] = ch[u][x];
        return flg;
    }
    void init() {
        n = cntNode;
        memset(maxSuf, 0, sizeof(maxSuf));
        make(-1), make(0);
    }
} t1, t2;

int main() {
    scanf("%s", str + 1);
    m = strlen(str + 1);
    t1.init(), t2.init();
    for(int i = 1; i <= m; ++i)
        t1.add(str[i] - 'a' + 1);
    for(int i = m; i >= 1; --i)
        t2.add(str[i] - 'a' + 1);
    for(int i = 1; i <= m - 1; ++i)
        ans += t1.sufCount[ t1.maxSuf[i] ]
                *
               t2.sufCount[ t2.maxSuf[m - i] ];
    printf("%lld", ans);
    return 0;
}

{% endfolding %}

警告

有关回文树的高级应用,请查阅论文。

(我咕了)

写在最后

回文树真的能很巧妙地解决与回文串有关的问题,

而且很多与回文串有关的问题的暴力的时间复杂度极劣无比,

这也能从侧面体现出回文树的巧妙。

用一首前人写的诗作结尾:

\[ \begin{aligned} & \textit{I think that I shall never see} \\\\ & \textit{A poem lovely as a tree.} \\\\ & \textit{Poems are made by fools like me,} \\\\ & \textit{But only God can make a tree.} \end{aligned} \]

接下来就开始努力钻研后缀树吧。