9

试图解决以下问题：

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

例如，如果输入字符串是ABCABCAB，那么正确的输出应该是ABC。你不能说ABCAB，因为这只会在两个子字符串重叠的地方发生两次，这是不允许的。

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

（在有人问之前，这不是功课。我正在寻找优化 Lindenmayer 分形渲染的方法，因为它们往往会花费大量时间来使用幼稚的海龟图形系统在高迭代级别进行绘制。）

4

4 回答 4

3

这是一个长度为 11 的字符串的示例，您可以对其进行概括

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

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

    左右
    偏移 偏移
     0 5
     0 6
     1 5
  • 如果你找到一个重复的，你就完成了。否则将块长度减少到 4 并重复直到块长度变为零。

这是一些（显然未经测试的）伪代码：

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

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

于 2012-08-07T20:53:22.163 回答
2

它看起来像一个后缀树问题。创建后缀树，然后找到具有多个子节点的最大压缩分支（在原始字符串中出现多次）。该压缩分支中的字母数应该是最大子序列的大小。

我在这里找到了类似的东西：http: //www.coderanch.com/t/370396/java/java/Algorithm-wanted-longest-repeating-substring

看起来它可以在 O(n) 中完成。

于 2012-08-07T20:52:15.103 回答
0

首先，我们需要定义子字符串的开始符号并定义长度。迭代所有可能的起始位置，然后找出长度，对长度进行二进制搜索（如果你能找到长度为 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;
        }
    }

说得通？

于 2012-08-07T20:39:56.677 回答
0

This type of analysis is often done in genome sequences. have a look at this paper. it has an efficient implemention (c++) for solving repeats: http://www.complex-systems.com/pdf/17-4-4.pdf might be what you are looking for

于 2013-05-21T15:00:33.357 回答