TRIE与回文树：算法分析与应用探讨

"IOI2017中国国家候选队论文集包含了多个信息学竞赛相关的研究论文，其中一篇由翁文涛撰写的论文讨论了回文树及其应用。回文树是一种数据结构，常用于处理回文串的问题。在TRIE（字典树）的基础上构建回文树，可以有效地找出所有有效字符串的回文子串。TRIE中的有效字符串是指从根节点到任意节点路径上的字符组合成的字符串。 论文中提到，一棵有n个节点的TRIE，其有效字符串的回文子串数量是O(n)的。这是因为在给定的字符串中，添加一个字符至父节点的字符串后面，最多只会增加一个回文子串，即该字符串的最长回文后缀。因此，回文树的大小也是线性的，可以用O(n log Σ)的时间复杂度构建，其中Σ表示字符集的大小。 在构建回文树的过程中，对于TRIE中的每个节点，记录其对应字符串的最长回文后缀在回文树上的节点。当扩展到子节点时，可以直接使用不基于势能分析的插入算法，快速找到子节点的最长回文后缀。 论文还探讨了一个有趣的问题，即如果使用最基础的插入算法来构建回文树，时间复杂度会是多少。定理4.1指出，这种情况下，算法的复杂度是O(所有叶子深度总和)，证明中通过分析节点的最长回文后缀在失败链接树（fail tree）上的深度，得出总势能消耗与所有叶子的深度总和成正比。 此外，这篇论文集还包括其他主题的研究，如数列递归式、线性代数在图匹配中的应用、多项式求和、独立集问题、动态传递闭包、特殊的分块算法、决策单调性动态规划、以及信息学竞赛中的命题报告等，展示了信息学竞赛中涉及的广泛理论和算法。"