4

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

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

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

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

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

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

最大重复对：S 中的一对相同的子串 alpha 和 beta，这样在任一方向上扩展 alpha 和 beta 都会破坏两个字符串的相等性它表示为三元组（位置 1，位置 2，长度）

最大重复：“出现在 S 中的最大对中的 S 的子串”。示例：S 中的 abc = xabcyiiizabcqabcyrxar。注意：可以有许多最大重复对，但只能有有限数量的最大重复。

超最大重复“永远不会作为任何其他最大重复的子串出现的最大重复”示例：S 中的 abcy = xabcyiiizabcqabcyrxar。

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

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

对于 S 中的每个位置 i，S(i-1) 称为左字符 i。T(S)中叶子的左字符是该叶子表示的后缀位置的左字符。如果在 v 的子树中至少有两个叶子具有不同的左字符，则 T(S) 中的内部节点 v 称为左分集。

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

当且仅当 v 的所有子节点都是叶子并且每个子节点都具有不同的左字符时，左多样化内部节点 v 表示超最大重复 a

字符串 A 和 B 可能都必须连接起来，当我们在第二步中检查 v 的叶子时，我们还必须施加一个额外的约束，即字符串 A 和 B 中必须至少有一个不同的左字符。这可以通过将它们的位置与 A 的长度进行比较。如果位置（左字符）> 长度（A），则左字符在 A 中，否则在 B 中。

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

4

1 回答 1

0

听起来您正在寻找两个输入字符串的所有子字符串的集合交集。在这种情况下，还应返回单字母子字符串。让 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 之间的字符。

于 2013-07-25T18:21:26.317 回答