2

我试图找到一种方法来找到一组字符串中最大的重复子字符串。最长重复子串问题通常适用于单个字符串，而不是一组字符串。什么类型的算法可用于在一组字符串中查找最大的重复子字符串？

在一组文件中查找最大的重复字符串（以删除大型软件库中的重复代码）是我想到的主要用例，但该算法也会有许多其他用例。

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

"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."将是最长的重复字符串（即出现在多个这些字符串中的最长字符串）。

4

3 回答 3

0
  1. Create a Trie data structure (a.k.a. a prefix tree) for each string
    • Let's call it T(i) for string i
  2. Create an empty hash map with key string and value int
    • Let's call it M
  3. For each Trie T(i), for each node P (where P is a prefix string) in T(i),
    • if key P is already in M, then increment M[P]
    • else, insert M[P] = 1
  4. Find the (P*,C*) pair in M such that:
    • C* >= 2 (*)
    • length(P*) is maximum among all such pairs
  5. P* is the string that you want

(*) If you wanted to get the longest substring common to K of the strings, you would replace the 2 with K

于 2013-05-27T02:11:40.567 回答
0

也许这就是您正在寻找的，但您需要将算法应用于两个以上的字符串。如果您考虑一下，这并不难。另外，看看这个页面。使用回溯不是一个好主意。

于 2013-03-06T22:38:16.873 回答
0

您的问题的答案从幻灯片 60 点击这里开始

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

于 2013-05-27T00:52:05.200 回答