14

我需要在字符串中找到最长的非重叠重复子字符串。我有可用的字符串的后缀树和后缀数组。

当允许重叠时，答案很简单（后缀树中最深的父节点）。

例如对于 String = "acaca"

如果允许重叠，则答案为“aca”，但不允许重叠时，答案为“ac”或“ca”。

我只需要算法或高级想法。

PS：我试过了，但在网上找不到明确的答案。

4

8 回答 8

4

生成后缀数组并在 O(nlogn).ps 中排序：有更有效的算法，如 DC3 和 Ukkonen 算法。例子：

字符串：ababc 后缀数组：子字符串的起始索引 | 子串
0 - ababc
2 - abc
1 - babc
3 - bc
4 - c

比较每两个连续的子串并得到具有以下约束的公共前缀：
说i1是子串“ ababc ”的索引：0
说i2是子串“ abc ”的索引：2
通用前缀是“ ab ”，公共前缀的长度是len

abs(i1-i2) >len //避免重叠

用解遍历后缀数组，得到“ababc”的结果，即“ ab ”；

整个解决方案将运行 O(nlogn)

但是，会有一个特殊情况：“aaaaa”，这个解决方案无法彻底解决。
欢迎讨论并提出解决方案 O(nlogn) 但不是 O(n^2)

于 2014-07-11T20:11:21.227 回答
3

不幸的是，Perkins 提出的解决方案行不通。我们不能强行通过解决方案来找到一个长时间重复的非重叠子字符串。考虑香蕉的后缀树：http ://en.wikipedia.org/wiki/Suffix_tree 。首先考虑以“A”为父节点的“NA”分支节点，因为它的长度最大并且是一个分支节点。但是它构造的字符串“ANA”是重叠的，所以会被拒绝。现在，要考虑的下一个节点是“NA”，它将显示非重叠长度为 2，但永远不会考虑子字符串“AN”，因为它已经在已经考虑的 ANA 字符串中表示。因此，如果您正在搜索所有重复的非重叠子字符串，或者当有'

显然有一种涉及后缀树的方法有效，但这里列出了更简单的方法：http ://rubyquiz.com/quiz153.html

希望这可以帮助！

于 2013-10-28T13:25:08.930 回答
2

通过构建后缀树，所有共享前缀 P 的后缀都将是树中共同祖先的后代。通过存储该子树的后缀的最大和最小索引，我们可以保证长度为 min(depth, max-min) 的重复非重叠子串，其中 max-min 是它们之间的距离，depth 是他们的共同前缀。期望值是具有最大该值的节点。

于 2015-09-25T12:31:38.777 回答
2

由于我很难找到一个工作算法的清晰描述，以使用后缀树获得最长的非重叠重复子字符串，我想分享我从各种来源收集的版本。

算法

  1. 为输入字符串S构造后缀树（以S中不出现的特殊字符结尾）。每个叶节点对应于 S 的一个后缀S i ，并被分配了S i在S中对应的起始位置i。
  2. 为树中的每个节点分配一对(i min , i max )，指示该子树处的最小和最大后缀索引。
    1. 对于每个叶子i min = i max = i。
    2. 对于每个内部节点， i min是最小值，i max是所有后代节点索引的最大索引。
  3. 对于所有内部节点v，让P v表示通过连接从根到v的路径上的所有边缘标签（前缀）获得的字符串。收集所有满足i min + length( P v ) ≤ i max的P v对应的i min和i max在v。
  4. 这些P v中最长的一个是S中至少出现两次的最长的非重叠子串。

解释

如果 S 的子串在S中至少出现两次，则它是两个后缀S i和S j的公共前缀P，其中i和j表示它们各自在S中的起始位置。因此，在S的后缀树中存在一个内部节点v ，它具有两个对应于i和j的后代叶子，使得从根到v的路径的所有边标签的串联等于P。

最深的此类节点v（就其对应前缀的长度而言）标记了S中最长的、可能重叠的重复子串。为了确保不考虑重叠子串，我们必须确保P不超过i和j之间的距离。

因此，我们计算每个节点的最小和最大索引i min和i max，它们对应于共享公共前缀的S的最左侧和最右侧后缀的位置。一个节点的最小和最大索引可以很容易地从其后代的值中获得。（如果我们要寻找至少出现k次的最长子串，则索引计算会更加复杂，因为必须考虑所有后代索引的距离，而不仅仅是相距最远的两个。）仅考虑满足i min + length( P ) ≤ i的前缀P最大我们确保从S i开始的P足够短，不会与后缀S j重叠。

补充说明

  • 长度为n的字符串的后缀树可以在 Θ( n ) 时间和空间内构建。对该算法的修改不会使渐近行为恶化，使得整体运行时间仍然在 Θ( n ) 中。
  • 该算法无法找到所有可能的解决方案。如果有多个不重叠的最长子串，则只找到从最大位置开始的子串。
  • 应该可以修改算法以计算最长不重叠子串的重复次数，或者只找到至少有k次重复的解决方案。为此，不仅要考虑最小和最大索引，还要考虑节点处所有子树的索引。然后必须为每个相邻的索引对保持上述范围条件。
于 2019-08-25T21:57:02.230 回答
1

最简单的解决方案是蛮力攻击。你有一个算法可以找到最长的允许重叠的字符串，使用它，检查那个答案是否有重叠，如果有，找到第二长的，检查它是否有重叠，等等。这将其减少为您现有的搜索算法，然后是正则表达式计数操作。

于 2012-09-30T04:06:33.143 回答
0

这可以使用“计算最长先前非重叠因子”中给出的结果来解决（参见http://dx.doi.org/10.1016/j.ipl.2010.12.005）

于 2013-09-25T18:46:34.367 回答
0

我们使用最长公共前缀（LCP）数组和后缀数组在 O(n log n) 时间内解决这个问题。

LCP 数组为我们提供了后缀数组中两个连续后缀之间的最长公共前缀。

构造完LCP数组和后缀数组后，我们就可以对答案的长度进行二分查找了。

假设字符串是“acaca$”。后缀数组在代码片段中以表格形式给出。

<table border="1">
<tr><th>Suffix Array index</th><th>LCP</th><th>Suffix (implicit)</th></tr>
<tr><td>5</td><td>-1</td><td>$</td></tr>
<tr><td>4</td><td>0</td><td>a$</td></tr>
<tr><td>2</td><td>1</td><td>aca$</td></tr>
<tr><td>0</td><td>3</td><td>acaca$</td></tr>
<tr><td>3</td><td>0</td><td>ca$</td></tr>
<tr><td>1</td><td>2</td><td>caca$</td></tr>
</table>

让我们对答案的长度进行二进制搜索。

如果我们有一定的答案，让两个子串对应两个后缀。

不能保证这些后缀在后缀数组中是连续的。但是，如果我们知道子字符串的长度，我们可以看到 LCP 表中两个子字符串后缀之间的每个条目都至少是那个数字。此外，两者的索引之间的差异必须至少是那个数字。

假设子字符串的长度是一定的，我们可以考虑连续运行的 LCP 数组条目至少是这个数量。在每次连续运行中，找到具有最大和最小索引的后缀。

我们怎么知道我们的猜测是一个下限？

如果某些 [至少是我们猜测的 LCP 数组条目的连续运行] 中最大和最小索引之间的距离至少是我们的猜测，那么，我们的猜测是一个可达到的下限。

我们怎么知道我们的猜测太大了？

如果所有 [至少是我们猜测的 LCP 数组条目的连续运行] 中最大和最小索引之间的距离小于我们的猜测，那么，我们的猜测太大了。

给定答案的长度，我们如何找到答案？

对于每个 [至少是答案的 LCP 数组条目的连续运行]，找到最低和最高索引。如果它们至少在答案上有所不同，那么我们返回最长的非重叠重复子字符串从这些索引开始。

在您的示例“acaca$”中，我们可以发现答案的长度为 2。

所有的runs都是：“aca$”，“acaca$”，下标和上标之间的距离是2，导致重复的子串“ac”。

"caca$", "ca$", 下标和上标之间的距离为 2，导致重复的子串 "ca"。

于 2017-04-05T23:32:00.390 回答
0

完整代码：

#include <bits/stdc++.h>
using namespace std;
int cplen(string a,string b){
    int i,to=min(a.length(),b.length());
    int ret=0;
    for(i=0;i<to;i++){
        if(a[i]==b[i])ret++;
        else {
            return ret;}
        }
    return ret;
    }
int main(){
    {
        int len,i;
        string str;
        cin>>str;
        len=str.length();
        vector<pair<string,int> >vv;
        map<char,int>hatbc;
        string pp="";
        for(i=len-1;i>=0;i--){
            hatbc[str[i]]++;
            pp=str.substr(i,len-i);
            vv.push_back(make_pair(pp,i));
            }
        if(len==1 || (int)hatbc.size()==len){
            printf("0\n");
            continue;
            }
        if(hatbc.size()==1){
            printf("%d\n",len/2);
            continue;
            }
        char prev=str[0];
        int foo=1,koo=0;
        for(i=1;i<len;){
            while(str[i]==prev && i<len){i++;foo++;}
            prev=str[i];
            i+=1;
            if(koo<foo)koo=foo;
            foo=1;
            }

        sort(vv.begin(),vv.end());
        int ans=0;
        ans=koo/2;
        for(i=1;i<(int)vv.size();i++){
            int j=i-1;
            int a=vv[j].second,b=vv[i].second;
            string sa=vv[j].first,sb=vv[i].first;
            int cpl;
            cpl=cplen(sa,sb);
            if(abs(a-b)>=cpl)
                ans=max(ans,cpl);
            }
        printf("%d\n",ans);
        }
    return 0;
    }

复杂性：O(n*log(n))（由于排序）

于 2016-03-25T20:41:20.823 回答