刚刚学习了最长公共子串算法，我对这个问题的一个特定变体感到好奇。其描述如下——
给定两个非空字符串序列，X = (x1, x2, x3,....,x(n)) 和 Y = (y1, y2, y3,..., y(m))，其中 x (i) 和 y(i) 是字符串，求longestX 中的字符串，它是allY 的字符串。
我有一个函数substring(x, y)它返回描述 x 是否是 y 中的子字符串的布尔值。显然，我必须将 Y 中的所有字符串连接起来形成一个大字符串，例如用 B 表示。我想到了以下方法 -：
-
Naive：首先连接 X 中的所有字符串形成字符串 A(n)。应用 substring(A(n), B) - 这包括在字符串 A(n) 中向后迭代。如果为 true，则算法在此结束并返回 A(n) - 或所述子字符串中包含的任何部分。如果不是，则继续应用 (A(n - 1), B)，依此类推。如果 X 中不存在这样的字符串，则返回空字符串。
显然，根据实现情况，这种方法会占用相当多的运行时间。假设我使用迭代方法，在每次迭代中我都必须向后迭代该级别/索引的字符串，然后应用 substring()。至少需要两个循环，并且O(size(B) * maxlength(x1, x2,...))最坏情况时间，或者更多取决于 substring() （如果错误请纠正我）。
我想到了第二种基于后缀树/数组的方法。
-
广义后缀树：我使用 Ukkonen 的算法构建了序列 Y 的 GST
O(maxlength(y1, y2,...)（？）。我对后缀树缺乏了解。我相信后缀树方法将大大减少查找子字符串的运行时间（以空间为代价），但我不知道如何实现该操作。
如果有更好的方法，我很想知道。
编辑：如果我似乎放弃了这个话题，我深表歉意。
如果我不使用 GST，而是使用一些标准数据结构（例如堆栈、队列、集合、堆、优先级队列等）怎么办？序列 X 必须进行排序，自然是最大的字符串在前。如果我将它存储在字符串数组中，我将不得不使用排序算法，例如归并排序/快速排序。目标是获得尽可能最有效的运行时间。
我是否可以将 X 存储在一个在构建自身时自动对其元素进行排序的结构中？最大堆怎么样？
后缀树似乎是以这种方式查找子字符串的最佳方法。还有其他我可以使用的数据结构吗？
首先，将最长字符串的数组 X 排序得更短。这样，X 中作为所有 Y 字符串的子字符串的第一个字符串就是解。
多处理器算法将是解决快速测试每个 X 字符串与所有 Y 字符串问题的最佳方法。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
