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

Question

试图解决以下问题:

给定一个任意长度的字符串,找到在字符串中出现多次的最长子字符串,没有重叠.

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

对于包含几千个字符的字符串,有没有办法合理快速地解决这个问题？

(而且在任何人问之前,这不是功课.我正在寻找优化Lindenmayer分形渲染的方法,因为它们倾向于花费过多的时间用一个天真的海龟图形系统在高迭代级别绘制.)

Answer 1

首先，我们需要定义子字符串的起始符号并定义长度。迭代所有可能的起始位置，然后通过二分搜索计算出长度（如果你能找到长度为 a 的 substr，你可能会发现长度较长，函数看起来单调，所以 bin 搜索应该没问题）。然后找到相等的子串是N，使用KMP或Rabin-Karp任何线性算法都可以。总计 N*N*log(N)。是不是太复杂了？代码是这样的：

for(int i=0;i<input.length();++i)
    {
        int l = i;
        int r = input.length();
        while(l <= r)
        {
            int middle = l + ((r - l) >> 1);
            Check if string [i;middle] can be found in initial string. Should be done in O(n); You need to check parts of initial string [0,i-1], [middle+1;length()-1];
            if (found)
                l = middle + 1;
            else
                r = middle - 1;
        }
    }

合理？