algorithm - 查找段落中的所有重复模式

Question

我手头有一个问题，我必须找到一个句子中存在的所有重复模式。

示例:'camel horse game camel horse gym camel horse game' # 这是经过清理的字符串，因为我将清理它之前的单词以外的任何内容。

['camel horse game', 0, 3, 6] # pattern and Index where it is repeated
['camel horse', 0, 3, 6] # Another pattern, let it be a substring of the previous pattern

后缀树是一个很好的解决方案，但我无法理解如何为 WORDS 而不是字母/字符实现它？

使用标准的Duplicate Substringss solution 将不起作用，因为它会找到带有缺口/半字的模式。 -> 'camel horse', 'amel hor' .... 'am h' 实际上没有任何用处。

提前致谢。

Answer 1

您可以为您喜欢的任何字母构建后缀树。想象一下，您创建了一个字母表，其中段落中的每个不同单词都被视为一个字母。然后，后缀树将让您在段落中找到重复的单词序列，而无需将单词拆分为单个字符。