如何使用后缀树算法查找大字符串中子字符串的位置？
How to find the position of a substring in a large string using suffix tree algorithm?
我从另一个堆栈溢出中学习了如何实现后缀树post。我只能知道子串是否存在。我想知道是否有一种方法可以使用后缀树找到子模式在字符串中的位置。
是的！后缀树叶通常用给定后缀开始的索引进行注释。因此，您可以通过为 T 构建后缀树，搜索 P，然后从搜索结束的节点开始执行 DFS，从而找到字符串 T 中所有出现的字符串 P。以这种方式找到的每一片叶子对应于字符串 P 出现的一个索引。另外，它运行得非常快：运行时间为 O(|P| + k)，其中 k 是匹配数。
我从另一个堆栈溢出中学习了如何实现后缀树post。我只能知道子串是否存在。我想知道是否有一种方法可以使用后缀树找到子模式在字符串中的位置。
是的！后缀树叶通常用给定后缀开始的索引进行注释。因此，您可以通过为 T 构建后缀树，搜索 P，然后从搜索结束的节点开始执行 DFS，从而找到字符串 T 中所有出现的字符串 P。以这种方式找到的每一片叶子对应于字符串 P 出现的一个索引。另外，它运行得非常快：运行时间为 O(|P| + k)，其中 k 是匹配数。