刚刚学习了最长公共(public)子串算法，我对这个问题的一个特定变体很好奇。描述如下-:
Given two non-empty sequences of strings, X = (x1, x2, x3,....,x(n)) and Y = (y1, y2, y3,..., y(m)), where x(i) and y(i) are strings of characters, find the longest string in X which is a substring of all the strings of Y.
我有一个函数 substring(x, y)，它返回 bool 值，表示 x 是否是 y 中的子字符串。显然，我必须将 Y 中的所有字符串连接起来形成一个大字符串，比方说，用 B 表示。我想到了以下方法-:
- 朴素:首先连接 X 中的所有字符串以形成字符串 A(n)。 Apply substring(A(n), B) - 这包括在字符串 A(n) 中向后迭代。如果为真，则算法在此结束并返回 A(n) - 或它的任何部分包含在所述子字符串中。如果不是，则继续申请 (A(n - 1), B) 等等。如果 X 中不存在这样的字符串，我将返回空字符串。
显然，这种方法会占用相当多的运行时间，具体取决于实现方式。假设我使用迭代方法，在每次迭代中我都必须在该级别/索引处向后迭代 String，然后应用 substring()。它至少需要两个循环，并且 O(size(B) * maxlength(x1, x2,...)) 最坏情况时间，或更多取决于 substring() (如果错误请纠正我) .
我想到了第二种基于后缀树/数组的方法。
- 广义后缀树:我在
O(maxlength(y1, y2,...)(?) 中使用 Ukkonen 算法构建序列 Y 的 GST。我缺乏后缀树咬合知识。我相信后缀树方法会大大减少查找子字符串的运行时间(以空间为代价)，但我不知道如何实现该操作。
如果有更好的方法，我很想知道。
编辑:如果我似乎放弃了这个话题，我深表歉意。
如果我不使用 GST，而是使用一些标准数据结构，如堆栈、队列、集合、堆、优先级队列等，会怎样？自然地，序列 X 必须排序，最大的字符串排在第一位。如果我将它存储在一个字符串数组中，我将不得不使用诸如 mergesort/quicksort 之类的排序算法。目标是尽可能获得最高效的运行时间。
我不能将 X 存储在一个结构中，该结构会在它构建自身时自动对其元素进行排序吗？最大堆怎么样？
后缀树似乎是以这种方式查找子字符串的最佳方式。我可以使用任何其他数据结构吗？
最佳答案
首先，将最长字符串的数组 X 排序为更短。这样，X 中第一个作为所有 Y 字符串的子字符串的字符串就是解决方案。
多处理器算法将是解决用所有 Y 字符串快速测试每个 X 字符串问题的最佳方法。
关于string - 两个字符串序列中的最长公共(public)子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19158025/