我看到了Wikipedia页面，但仍然不清楚。
为了找到2个字符串(T和S)的最长公共(public)子字符串，我读到必须为字符串T($1)S($2)构建后缀树，其中($ 1)和($ 2)是不是字符串一部分的特殊字符。
但是维基百科上字符串ABAB和BABA的图像如下所示:
为什么不包含整个字符串ABAB($1)BABA($2)？它不是连接字符串的后缀吗？
叶子上的那些数字是多少？
最佳答案
广义后缀树是后缀树的一种变体，其中存储了两个(或更多)不同字符串T1和T2的后缀，而不仅仅是一个字符串T的后缀。
生成广义后缀树的一种方法是开始制作一个T1 $ 1T2 $ 2后缀树。生成的后缀树将包含T1和T2的所有后缀，但它还将包含许多从T1开始并传播到T2的“虚假”后缀。要解决此问题，在构建初始后缀树之后，通常需要对树结构进行第二遍处理，并消除任何超出$ 1标记的后缀。例如，这就是为什么您在上面给出的广义后缀树不包含ABAB $ 1BABA $ 2。
关于您的下一个问题-叶子上的数字是多少？ -后缀树中的每个叶子通常都用叶子所对应的后缀的开始索引进行标记。在广义后缀树中，每个叶子都用两条信息标记-后缀的开始索引以及后缀所属的字符串。叶子上的符号a:b表示“此后缀来自字符串a，并且从该字符串的索引b开始”。例如，最左边的叶子上的标记1:3表示“此后缀来自字符串1，并且从位置3开始。”您可以看到，它对应于后缀A $ 1，它的确从ABAB $ 1的位置3开始，并假设为1索引。
希望这可以帮助!
关于string - 什么是广义后缀树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20871770/