我需要找到一个字符串中最长的非重叠重复子。 我有字符串的后缀树和后缀阵列可用。
当被允许重叠，答案是微不足道的（在后缀树最深父节点）。
例如，对于字符串=“ACACA”
如果重叠是允许的答案是“ACA”，但重叠是不允许的答案时，“AC”或“CA”。
我需要的算法或只有高层次的想法。
PS：我试过，但没有明确的答案，我可以找到网页。
Answer 1:
生成后缀数组和排序在O（nlogn）.PS：有更有效的算法像DC3和Ukkonen算法。 例：
字符串：ababc后缀数组：字符串的开始，指数| 子
0 - ababc
2 - ABC
1 - BABC
3 - 公元前
4 - Ç
比较每两个连续串并获得具有以下约束共同的前缀：
说I1是串“ababc”的指数：0
说I2是子“ABC”的指数：2
共同的前缀是“AB”，共同的前缀的长度为LEN
ABS（I1-I2）> LEN //避免重叠
经过后缀阵列的解决方案，你会得到“ababc”，这是“AB”的结果;
整个解决方案将运行O（nlogn）
然而，将有一个特殊情况：“AAAAA”，这种解决方案不能彻底解决。
欢迎大家讨论，并拿出为O（nlogn）的解决方案，但不是为O（n ^ 2）
Answer 2:
不幸的是，帕金斯提出的解决方案是行不通的。 我们不能蛮力我们的方式，通过解决方案，以找到一个长期反复的非重叠子。 考虑香蕉后缀树： http://en.wikipedia.org/wiki/Suffix_tree 。 用“A”作为其父的“NA”分支节点将被首先考虑，因为它有最大的长度，并且是分支节点。 但其构造的字符串“ANA”是重叠的，所以它会被拒绝。 现在，下一个节点考虑与被“NA”，这将显示2非重叠的长度，但串“AN”将永远不会被考虑，因为它是在已经考虑的ANA串已经表示。 所以，如果你正在寻找所有重复的非重叠子，或者当有希望第一个字母一个领带，你的运气了。
显然有涉及后缀树的方法这样的作品，但更简单的方法在这里布局： http://rubyquiz.com/quiz153.html
希望这可以帮助！
Answer 3:
最简单的办法是蛮力攻击的东西。 你有一个算法来找出最长的重叠允许的字符串，使用它，检查这个问题的答案有重叠，如果是的话，找到第二个最长的检查，看看它是否有重叠，等等。 它减少到现有的搜索算法，然后一个正则表达式计数操作。
Answer 4:
通过构建一个后缀树，所有后缀共享一个前缀P将是树一个共同的祖先的后代。 通过存储的最大值和该子树的后缀的最小索引，就能保证的长度分（深度，最大 - 最小）其中max-min是它们与深度之间的距离的重复的非重叠子是长度他们共同的前缀。 所期望的值与最大这样的值的节点。
Answer 5:
这可利用“计算最长以前不重叠的因素”给出的结果来解决（见http://dx.doi.org/10.1016/j.ipl.2010.12.005 ）
Answer 6:
完整的代码：
#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））（由于排序）
Answer 7:
我们使用时间最长的公共前缀（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。
所有的运行是：“ACA $”，“ACACA $”，以及较低和较高的指数之间的距离是2，导致重复串“交流”。
“CACA $”，“CA $”，和较低和较高的索引之间的距离为2，从而在重复子串“CA”。
文章来源: Longest Non-Overlapping Repeated Substring using Suffix Tree/Array (Algorithm Only)
