两个字符串序列中最长的公共子字符串
刚刚学习了最长的公共子串算法，我对这个问题的一个特定变体感到好奇。 它被描述如下 - ：
给定两个非空字符串序列，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表示。我想到了以下方法：
很明显，这种方法会占用相当长的时间，具体取决于实施情况。 假设我使用迭代方法，每次迭代时都必须在该级别/索引处向后迭代字符串，然后应用substring（）。 这将需要至少两个循环，并且O(size(B) * maxlength(x1, x2,...))最坏情况时间，或者更多取决于substring（）（纠正我，如果错误的话）。
我想到了基于后缀树/数组的第二种方法。
O(maxlength(y1, y2,...) （？）中的Ukkonen算法构建序列Y的GST。我对后缀树的缺乏了解，我相信后缀树方法会大大减少运行用于查找子字符串的时间（以空间为代价），但我不知道如何实现该操作。 如果有更好的方法，我很想知道。
编辑：道歉，如果它似乎我放弃了这个话题。
如果我不是使用GST，而是使用一些标准的数据结构，如堆栈，队列，集合，堆，优先级队列等，该怎么办？ 序列X必须先排序，最大的字符串是自然排序的。 如果我将它存储在一个字符串数组中，我将不得不使用排序算法，如mergesort / quicksort。 目标是尽可能获得最有效的运行时间。
我能不能将X存储在一个结构中，该结构可以在构建自身时自动对其元素进行排序？ 怎么样一个最大堆？
似乎后缀树是以这种方式查找子串的最佳方式。 有没有其他数据结构可以使用？
首先，让数组X最长的字符串变短。 这样，X中的第一个字符串就是解决方案，它是所有Y字符串的子字符串。
多处理器算法将是解决快速测试每个X字符串与所有Y字符串的问题的最佳方法。
这里是我对你的问题的解决方案的想法; 我不确定所有事情，所以如果您认为值得付出努力，欢迎您提出改进意见。
首先计算Y中所有字符串的所有常见子字符串。首先取两个字符串，然后构建一个包含所有常见子字符串的树。 然后，对于Y中的每个其他字符串，从映射中移除未出现在此字符串中的每个子字符串。 复杂度与Y中的字符串数量成线性关系，但我无法弄清楚树中有多少元素，所以我无法估计最终的复杂度。
然后找到X中最长的字符串，它是树中的一个子字符串。
必须做一些改进才能使树尽可能小，例如只保留不是其他子串的子串。
写| Y | 对于集合Y中的字符串数量，len（Y）对于它们的总长度：
将Y中的字符串处理为通用后缀树（例如，使用Ukkonen算法）。 花时间O（len（Y）），假设一个恒定大小的字母表。
根据该节点标识的字符串是否属于Y中的所有字符串，标记后缀树中的每个节点。耗时O（| Y | len（Y））。
对于X中的每个字符串，请在后缀树中查找它，并查看该节点是否被标记为属于Y中的所有字符串。输出最长的此类标记字符串。 花时间O（len（X））。
总时间：O（| Y | len（Y））+ O（len（X））。
链接地址: http://www.djcxy.com/p/16305.html