从 trie 中检索丢失的字符串
Retrieving a lost string from a trie
在数据结构考试中，我确实看到了以下问题：
给出了后缀特里。
现在我知道 trie 只包含指向字符数组的具有特定索引的指针。
现在他们说原来的字符串丢失了，我应该只用trie就可以找到字符串。
看不懂，怎么可能？
您可以为后缀树提供相似的字符串和通配符。我知道最长的子序列和 aho-corasick 算法是可能的。
后缀特里树是一种特殊的数据结构，可以看作是一个自动机。
由于这是一个后缀 trie 而不是后缀 tree，因此原始字符串的每个子字符串在 trie 中都有一个显式状态代表它。
trie 的任何叶子将表示原始字符串的特定后缀。由于原始字符串是其自身最长的后缀，trie中有一片叶子代表原始字符串，它是trie中最深的叶子
要恢复原始字符串，只需从根开始进行BFS，直到找到最深的叶子。复杂度为 O(N²) 其中 N 是原始字符串的长度（因为后缀特里树中的节点数是 O(N²)).
编辑：在被否决后，我坚持认为我们正在研究 后缀特里 ，NOT 后缀树。这些数据结构是相似的，没错，但它们 NOT 相同！后缀特里树明确表示其原始字符串的 EVERY 个子字符串。另一方面，后缀树仅表示后缀树的 分支状态 。
现在，一个字符串中可以有多少个不同的子字符串？ 1 个长度为 N 的子串，2 个长度为 N-1，3 个长度为 N-2， ... 总计 N(N+1)/2 = O(N²).
在数据结构考试中，我确实看到了以下问题：
给出了后缀特里。 现在我知道 trie 只包含指向字符数组的具有特定索引的指针。
现在他们说原来的字符串丢失了，我应该只用trie就可以找到字符串。 看不懂，怎么可能？
您可以为后缀树提供相似的字符串和通配符。我知道最长的子序列和 aho-corasick 算法是可能的。
后缀特里树是一种特殊的数据结构，可以看作是一个自动机。 由于这是一个后缀 trie 而不是后缀 tree，因此原始字符串的每个子字符串在 trie 中都有一个显式状态代表它。
trie 的任何叶子将表示原始字符串的特定后缀。由于原始字符串是其自身最长的后缀，trie中有一片叶子代表原始字符串，它是trie中最深的叶子
要恢复原始字符串，只需从根开始进行BFS，直到找到最深的叶子。复杂度为 O(N²) 其中 N 是原始字符串的长度（因为后缀特里树中的节点数是 O(N²)).
编辑：在被否决后，我坚持认为我们正在研究 后缀特里 ，NOT 后缀树。这些数据结构是相似的，没错，但它们 NOT 相同！后缀特里树明确表示其原始字符串的 EVERY 个子字符串。另一方面，后缀树仅表示后缀树的 分支状态 。
现在，一个字符串中可以有多少个不同的子字符串？ 1 个长度为 N 的子串，2 个长度为 N-1，3 个长度为 N-2， ... 总计 N(N+1)/2 = O(N²).