algorithm - 我们可以在后缀树中使用圆形字符串吗？

Question

我们可以用带后缀树的循环字符串吗？
所以最后一个字符后面跟着列表中的第一个字符。
如果是，这个后缀树的表示与普通后缀树有何不同？

Answer 1

这取决于你所说的“使用”是什么意思。
（一）
首先，以最直接的方式解释你的问题，考虑一个长度为n的循环字符串，即每n个字符重复一次的无限字符串。这样一个对象没有通常意义上的后缀，因为它永远不会结束，所以您不能构造它的后缀树。
2）然而，我们的想法当然是，我们有一个有限的圆字符串表示，它使用从最后一个字符到第一个字符的链接。以类似的方式，我们可以通过使用指向表示循环字符串的所有（无限长）后缀的循环后缀树的链接来扩展给定的后缀树。注意，这不能通过插入从每个叶到节点根的链接来完成，因为从根开始，字符串的所有后缀都有传出边，但是从这样一个循环字符串的叶开始，只能有一个传出边示例：表示“missippi$”后缀“ssippi$”的叶应该有一个带无限标签“missippi$missippi$…”的传出边，并且没有其他边如果将其链接到树的根，则会有更多不正确的延续。
所以有两件事是必要的：
叶子的边缘（这毕竟是一个有趣的概念）。每片叶子都有一个向外的边缘。
带有无限标签的边。这个标签可以表示为循环字符串（并且循环字符串对于叶的所有传出边都是相同的）。
这将为循环字符串的所有（无限）后缀提供一个有效的表示。
3）我不确定这种表述是否有用。如果构造后缀树的目的是启用子字符串搜索，那么将循环字符串（不包括链接）的有限表示连接到其自身并由此构造后缀树的常用技巧就足够了，除非您搜索的子字符串本身超过n个字符。
还要注意的是，后缀树的某些其他用途需要引入更多的“无限”概念。例如，对于某些应用，可能需要在该节点中存储树节点的字符深度（即从根到特定节点的边缘标签的组合长度）。在上面提出的“循环后缀树”中，叶子的外边缘会导致某种特殊的“限制中的叶子”，并带有一个循环字符串作为标签。任何匹配到这样一个循环字符串中的查询都需要一种特殊的方式来跟踪匹配的深度，因为该边上没有内部节点来存储深度信息。
4）在说了所有这些之后，实际上至少有一个已知的后缀树应用于循环字符串，但不是在上面（1），（2）或（3）的意义上，即通过使用后缀树来表示整个无限对象。相反，一个后缀树的有限子串的圆形字符串被用来解决字典最小旋转问题。这个问题在Wikipedia中有描述，尽管这里列出的解决方案不包括任何使用后缀树的解决方案。但是，Dan Gusfield在7.13节的Algorithms on Strings, Trees and Sequences中描述了该解决方案。
其思想是，考虑一组长度为n的字符串S的字典式最小旋转，相当于一个循环字符串的第一个长度-N子串的集合。这个问题就相当于找到一个字典上最小的截止点。古斯菲尔德通过构造字符串SS $的后缀树来解决这个问题，通过在每个节点处取字典最小的边遍历该树，从而终止于对应于字典上最小的截止点的节点。
因此，如（4）所示，后缀树在循环字符串上下文中有一些实际的“用途”，但我不确定这是否是您感兴趣的用途。