algorithm - 使用后缀数组查找两个输入字符串的一组重复的、不重叠的子字符串

Question

输入:两个字符串A和B。

输出:一组重复的、不重叠的子串

我必须找到所有重复的字符串，每个字符串都必须在两个(!)字符串中至少出现一次。例如，让

A = "xyabcxeeeyabczeee"和 B = "yxabcxabee"。

那么有效的输出将是 {"abcx","ab","ee"} 而不是 "eee"，因为它只出现在字符串 A 中。

我认为这个问题与“超极大重复”问题非常相关。这是一个定义:

Maximal repeated pair : A pair of identical substrings alpha and beta in S such that extending alpha and beta in either direction would destroy the equality of the two strings It is represented as a triplet (position1,position2, length)

Maximal repeat : “A substring of S that occurs in a maximal pair in S”. Example: abc in S = xabcyiiizabcqabcyrxar. Note: There can be numerous maximal repeated pairs, but there can be only a limited number of maximal repeats.

Supermaximal repeat “A maximal repeat that never occurs as a substring of any other maximal repeat” Example: abcy in S = xabcyiiizabcqabcyrxar.

“关于字符串、树和序列的算法”中描述了一种用于查找所有超最大重复的算法，但仅适用于后缀树。

它的工作原理是:1.) 使用 DFS 找到所有左分集节点

For each position i in S, S(i-1) is called the left character i. Left character of a leaf in T(S) is the left character of the suffix position represented by that leaf. An internal node v in T(S) is called left-diverse if at least two leaves in v’s subtree have different left characters.

2.) 在这些节点上应用定理 7.12.4:

A left diverse internal node v represents a supermaximal repeat a if and only if all of v's children are leaves, and each has a distinct left character

字符串 A 和 B 可能都需要连接，当我们检查 v 的叶子时在第二步中，我们还必须施加一个额外的约束，即必须有字符串 A 和 B 中至少有一个不同的左侧字符。这可以通过比较来完成它们相对于 A 长度的位置。如果位置(左字符)> 长度(A)，则左字符在 A 中，否则在 B 中。

你能帮我解决这个后缀+lcp数组的问题吗？

Answer 1

听起来您正在寻找两个输入字符串的所有子字符串的集合交集。在这种情况下，还应返回单字母子字符串。让 s1 和 s2 成为您的字符串，s1 是两者中较短的一个。对此做了一些思考之后，我认为没有比直观的 O(n^3m) 或 O(n^3) 算法更好的方法了，其中 n 是 s1 的长度，m 是长度s2。我不认为后缀树可以在这里帮助你。

for(int i=0 to n-1){
    for(int j=1 to n-i){
        if(contains(s2,substring(s1,i,j))) emit the substring
    }
}

运行时来自 (n^2)/2 次循环迭代，每次执行最坏情况下的 O(nm) 包含操作(可能是 O(n)，具体取决于实现)。但它并没有那么糟糕，因为会有一个比前面的 1 小得多的常数，因为子串的长度实际上在 1 到 n 之间。
如果您不想要单个字符匹配，您可以将 j 初始化为 2 或更高的值。

顺便说一句:实际上不要用子字符串创建新字符串，查找/创建一个包含索引和原始字符串的包含函数，只查看之间的字符，包括 i，不包括 j。