我从另一个堆栈溢出帖子中学习了如何实现后缀树。我只能知道子串是否存在。我想知道是否有一种方法可以使用后缀树找到子模式在字符串中的位置。
最佳答案
是的!后缀树叶通常用给定后缀开始的索引进行注释。因此，您可以通过为 T 构建后缀树，搜索 P，然后从搜索结束的节点开始执行 DFS，从而找到字符串 T 中所有出现的字符串 P。以这种方式找到的每一片叶子对应于字符串 P 出现的一个索引。另外，它运行得非常快:运行时间为 O(|P| + k)，其中 k 是匹配项的数量。
关于algorithm - 如何使用后缀树算法查找大字符串中子字符串的位置？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32217588/