查找一组字符串中重复最长的子字符串

Question

我正在尝试寻找一种方法来找到一组字符串中最大的重复子字符串。longest duplicate substring problem通常适用于单个字符串，而不是一组字符串。在一组字符串中查找最大的重复子字符串时，哪种类型的算法是有用的？

在一组文件中查找最大的重复字符串(以便删除大型软件库中的重复代码)是我考虑的主要用例，但此算法还有许多其他用例。

例如，我希望在这组字符串中找到最长的重复子字符串：

"Hello world, this is the first string."
"Hello to the world, this is the second string."
"Hello world.  This is the third string."
"This is the third string."

在这种情况下，"This is the third string."将是最长的重复字符串(即，出现在这些字符串中的最长字符串)。

Answer 1

也许this就是您正在寻找的，但是您需要将该算法应用于两个以上的字符串。如果你仔细想想，这并不难。另外，请看一下this page。使用回溯不是一个好主意。

Answer 2

您的问题的答案是从幻灯片60 Click here开始

基本上，我们列出了字符串输入的所有可能后缀(线性时间)。对它们进行排序(NLogN)，并通过排序列表(线性时间)找到最长的一个

Answer 3

1. Create a Trie data structure (也称为前缀树)对于每个字符串，让我们将其称为string i

• T(i)

​

1. 创建一个包含键string和值int
   • 的空散列映射让我们称其为M

​

对于每个Trie

• ，对于T(i)中的每个节点P (其中P是前缀字符串)，如果<T(i)>d31>中已经存在关键字

• ，则递增M[P]

• else，insert M[P] = 1

​

在所有这样的pairs中，

1. 在(P*,C*)中找到M对，使得：
   • C* >= 2 (*)
   • length(P*)是最大的

​

1. P*是您希望

使用的字符串

(*)如果您想要获取字符串中K共有的最长的子字符串，您可以用K替换2