7

刚刚学习了最长公共子串算法，我对这个问题的一个特定变体很好奇。描述如下——

给定两个非空字符串序列，X = (x1, x2, x3,....,x(n)) 和 Y = (y1, y2, y3,..., y(m))，其中 x (i) 和 y(i) 是字符串，求X 中最长的字符串，它是Y的所有字符串的子串。

我有一个函数substring(x, y)，它返回描述 x 是否是 y 中的子字符串的布尔值。显然，我必须连接 Y 中的所有字符串以形成一个大字符串，例如，用 B 表示。我想到了以下方法 - ：

  • 朴素：首先连接 X 中的所有字符串以形成字符串 A(n)。应用 substring(A(n), B) - 这包括在字符串 A(n) 中向后迭代。如果为真，则算法在此处结束并返回 A(n) - 或包含在所述子字符串中的任何部分。如果不是，则继续申请 (A(n - 1), B) 等等。如果 X 中不存在这样的字符串，则返回空字符串。

显然，这种方法会占用相当多的运行时间，具体取决于实现。假设我使用迭代方法，在每次迭代中，我必须在该级别/索引处向后迭代字符串，然后应用 substring()。这将需要至少两个循环，以及O(size(B) * maxlength(x1, x2,...))最坏情况下的时间，或者更多取决于 substring() （如果错误，请纠正我）。

我想到了基于后缀树/数组的第二种方法。

  • 广义后缀树O(maxlength(y1, y2,...)：我在(?)中使用 Ukkonen 算法构建了序列 Y 的 GST 。我对后缀树咬伤的知识缺乏。我相信后缀树方法会大大减少查找子字符串的运行时间（以空间为代价），但我不知道如何实现该操作。

如果有更好的方法，我很想知道。

编辑：抱歉，如果我似乎放弃了这个话题。

如果我不使用 GST，而是使用一些标准数据结构，例如堆栈、队列、集合、堆、优先级队列等，该怎么办？必须对序列 X 进行排序，首先是最大的字符串。如果我将它存储在一个字符串数组中，我将不得不使用诸如mergesort/quicksort之类的排序算法。目标是尽可能获得最有效的运行时间。

我不能将 X 存储在一个结构中，该结构会在其自身构建时自动对其元素进行排序？最大堆呢？

后缀树似乎是以这种方式查找子字符串的最佳方式。我可以使用其他任何数据结构吗？

4

3 回答 3

1

Here is my idea about a solution of your problem; I am not sure about everything so comments are welcome to improve it if you think it worths the effort.

Begin with computing all common substrings of all strings in Y. First take two strings, and build a tree of all common substrings. Then, for each other string in Y, remove from the map every substring that does not appear in this string. The complexity is linear with the number of strings in Y, but I can't figure out how many elements might be in the tree so I cannot draw an estimation of the final complexity.

Then find the longest string in X which is a substring of one in the tree.

There must be some improvements to do to keep the tree as small as possible, such as keeping only substrings that are not substrings of others.

于 2013-10-03T12:07:43.907 回答
1

首先，将最长字符串的数组 X 排序为更短。这样，X 中作为所有 Y 字符串的子字符串的第一个字符串就是解决方案。

多处理器算法将是解决用所有 Y 字符串快速测试每个 X 字符串问题的最佳方法。

于 2013-10-03T12:00:03.323 回答
1

写作 |Y| 对于集合 Y 中的字符串数，以及它们的总长度 len(Y)：

  1. 将 Y 中的字符串处理成广义后缀树（例如，使用Ukkonen 算法）。假设一个恒定大小的字母表，花费时间 O(len(Y))。

  2. 根据该节点标识的字符串是否属于Y中的所有字符串来标记后缀树中的每个节点。耗时O(|Y|len(Y))。

  3. 对于X中的每一个字符串，在后缀树中查找，看看该节点是否被标记为属于Y中的所有字符串。输出最长的这样标记的字符串。花费时间 O(len(X))。

总时间：O(|Y| len(Y)) + O(len(X))。

于 2013-10-03T12:16:15.907 回答