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

Question

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

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

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

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

那么一个有效的输出将是{"abcx“、"ab”、"ee"}，而不是"eee"，因为它只发生在字符串A中。

我认为这个问题与“超极大重复”问题有很大关系。以下是一个定义：

最大重复对:S中的一对完全相同的子串α和β，使α和β向任意方向扩展都会破坏两个字符串的相等，它被表示为三重奏(position1、position2、length)。 最大重复：“在S中的最大对中出现的S的子串”。例子: abc在S= xabcyiiizabcqabcyrxar。注:可以有许多最大重复对，但只能有有限数量的最大重复。 超极大重复“从不作为任何其他最大重复的子串出现的最大重复”示例: abcy in S= xabcyiiizabcqabcyrxar。

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

它的工作原理是:1)使用DFS查找所有左转节点。

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

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

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

两个字符串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到n之间。

如果不需要单个字符匹配，则只需将j初始化为2或更高的值。

顺便说一句:不要实际创建带有子字符串的新字符串，查找/创建一个包含函数，该函数将接受指示符和原始字符串，只需查看包含i (不包括j )之间的字符。