Ukkonen 的后缀树构造 – 第一部分
后缀树在许多字符串处理和计算生物学问题中非常有用。许多书籍和电子资源从理论上讨论了它，只有少数地方讨论了代码实现。但是，我仍然觉得缺少了一些东西，而且实现代码来构造后缀树及其在许多应用程序中的使用并不容易。这是试图弥合理论与完整工作代码实现之间差距的尝试。在这里，我们将讨论 Ukkonen 的后缀树构造算法。我们将从理论到实现，分多个部分逐步详细讨论它。我们将从蛮力开始，尝试理解 Ukkonen 算法中涉及的不同概念和技巧，并在最后一部分讨论代码实现。
注意：您可能在第一次或第二次阅读时发现算法的某些部分难以理解，这完全没问题。再尝试和思考几次，您应该能够理解这些部分。
m 个字符的字符串 S 的后缀树T是一棵有根有向树，有 m 个叶子，编号从 1 到m。（假设最后一个字符串字符在字符串中是唯一的）
- Root 可以有零个、一个或多个子节点。
- 除根之外的每个内部节点都至少有两个子节点。
- 每条边都用 S 的非空子字符串标记。
- 来自同
原文地址：https://blog.csdn.net/tianqiquan/article/details/140601372
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！