string - 寻找 MEM 的高效算法

Question

MEM是“Maximum Exact Matching”问题的缩写，该问题的目的是找出两个输入字符串之间的所有最大相似子串。请注意，此问题与字符串匹配问题(或文本搜索)略有不同，您希望在另一个文本中找到给定的字符串。

例如，在以下两个字符串中(具有有限的 charcharchers { 1,2,3})，MEM 是“12”和“3312”

str1:"12233312"

str2:"123312"

例如 233 也是两个输入字符串之间的公共(public)子串，但由于有另一个更大的子串包含它，我们不认为它是 MEM。

有没有人有一些优雅的想法如何解决它。一个非常简单的想法是使用搜索算法在大字符串中使用一些快速字符串搜索算法(如 Boyer–Moore)查找较小字符串的所有可能子字符串。但这似乎不是处理这个问题的有效方法。

Answer 1

这是一个线性时间算法。

1. 在str1 + "X"+ str2上构建后缀树，其中'X'没有出现在str1中或者str2.

2. 一些叶节点对应于以 str1 开头的后缀(包含 'X')。给这些涂上红色。将其他颜色涂成蓝色。

3. 从根到叶遍历树，用从根到它的字符串长度标记每个节点。

4. 从叶到根遍历树，找到同时具有红色后代和蓝色后代的最叶节点。第三步计算出的label就是公共(public)子串的长度。