string - 如何找到至少重复一次的字符串中的最大序列？

Question

尝试解决以下问题:

Given a string of arbitrary length, find the longest substring that occurs more than one time within the string, with no overlaps.

例如，如果输入字符串是 ABCABCAB，则正确的输出将是 ABC。您不能说 ABCAB，因为这只会在两个子字符串重叠的地方出现两次，这是不允许的。

对于包含几千个字符的字符串，有什么方法可以相当快速地解决这个问题吗？

(在有人问之前，这不是家庭作业。我正在寻找优化 Lindenmayer 分形渲染的方法，因为它们往往需要花费过多的时间来使用朴素的海龟图形系统在高迭代级别上绘制。 )

Answer 1

这里有一个长度为 11 的字符串的例子，你可以概括

• 将 block 长度设置为 floor(11/2) = 5

• 扫描剩余 5 个字符的 block 中的字符串以查找重复项。会有3次比较

    Left      Right
    Offset    Offset
     0         5
     0         6
     1         5

• If you found a duplicate you're done. Otherwise reduce the chunk length to 4 and repeat until chunk length goes to zero.

Here's some (obviously untested) pseudocode:

String s
int len = floor(s.length/2)
for int i=len; i>0; i--
    for j=0; j<=len-(2*i); j++
        for k=j+i; k<=len-i; k++
            if s.substr(j,j+i) == s.substr(k,k+i)
                return s.substr(j,j+i)
return null

那里可能存在差一错误，但该方法应该是合理的(并且是最小的)。