两个字符串序列中最长的公共子字符串

Question

刚刚学习了最常见的子串算法,我对这个问题的特定变体感到好奇.它描述如下 - :

给定两个非空的字符串序列,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).应用子串(A(n),B) - 这包括在字符串A(n)中向后迭代.如果为true,则算法在此结束并返回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存储在一个自动对其元素进行排序的结构中？最大堆怎么样？

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

Answer 1

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

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