我正在尝试实现Evgeny Kluev在他对loop rolling algorithm的回答中给出的算法
但我很难让它工作。下面是一个我按照他的指示用手做的例子：
text: ababacababd
<STEP 1>
suffixes and LCPs:
ababacababd
4
ababd
3
abacababd
2
abd
1
acababd
0
babacababd
3
babd
2
bacababd
1
bd
0
cababd
0
d
<STEP 2>
sorted LCP array indices: 0,1,5,2,6,3,7,4,8,9
(values) : 4,3,3,2,2,1,1,1,0,0
<STEP 3>
LCP groups sorted by position in text (format => position: entry):
lcp 4:
0: ababacababd
6: ababd
lcp 3:
1: babacababd
2: abacababd
6: ababd
7: babd
lcp 2:
2: abacababd
3: bacababd
7: babd
8: abd
lcp 1:
3: bacababd
4: acababd
8: abd
9: bd
lcp 0:
0: ababacababd
1: babacababd
4: acababd
5: cababd
9: bd
10: d
<STEP 4>
entries remaining after filter (LCP == positional difference):
none! only (abd),(bd) and (bacababd),(acababd) from LCP 1 group
have positional difference equal to 1 but they don't share prefixes
with each other. shouldn't i have at least (ab) and (ba) here?
有人能告诉我在这个过程中我做错了什么吗？
另外，他说在第4步的末尾，我们应该有文本中所有可能的序列，他是说所有可能的重复序列吗？
这是一个已知的算法，它的名字我可以在其他地方找到更多的细节吗？
（我也对他在步骤5中对相交序列的定义感到困惑，但如果我正确理解前面的步骤，也许这是有意义的）。
编辑：以下是在Evgeny的帮助澄清之后，我对步骤4、5、6所做的：
<STEP 4>
filter pseudocode:
results = {}
for (positions,lcp) in lcp_groups:
results[lcp] = []
while positions not empty:
pos = positions.pop(0) #pop lowest element
if (pos+lcp) in positions:
common = prefix(input, pos, lcp)
if common.size() < lcp:
next
i = 1
while (pos+lcp*(i+1)) in positions:
if common != prefix(input, pos+lcp*i, lcp):
break
positions.delete(pos+lcp*i)
i += 1
results[lcp].append( (common, pos, i+1) )
application of filter logic:
lcp 4:
0: ababacababd # 4 not in {6}
6: ababd # 10 not in {}
lcp 3:
0: ababacababd # 3 not in {1,2,6,7}
1: babacababd # 4 not in {2,6,7}
2: abacababd # 5 not in {6,7}
6: ababd # 9 not in {7}
7: babd # 10 not in {}
lcp 2:
0: ababacababd # 2 in {1,2,3,6,7,8}, 4 not in {1,2,3,6,7,8} => ("ab", 0, 2)
1: babacababd # 3 in {2,3,6,7,8}, 5 not in {2,3,6,7,8} => ("ba", 1, 2)
2: abacababd # 4 not in {3,6,7,8}
3: bacababd # 5 not in {6,7,8}
6: ababd # 8 in {7,8}, 10 not in {7,8} => ("ab", 6, 2)
7: babd # 9 not in {8}
8: abd # 10 not in {}
lcp 1:
0: ababacababd # 1 in {1,2,3,4,6,7,8,9}, prefix is ""
1: babacababd # 2 in {2,3,4,6,7,8,9}, prefix is ""
2: abacababd # 3 in {3,4,6,7,8,9}, prefix is ""
3: bacababd # 4 in {4,6,7,8,9}, prefix is ""
4: acababd # 5 not in {6,7,8,9}
6: ababd # 7 in {7,8,9}, prefix is ""
7: babd # 8 in {8,9}, prefix is ""
8: abd # 9 in {9}, prefix is ""
9: bd # 10 not in {}
sequences: [("ab", 0, 2), ("ba", 1, 2), ("ab", 6, 2)]
<STEP 5>
add sequences in order of LCP grouping. sequences within an LCP group
are added according to which was generated first:
lcp 4: no sequences
lcp 3: no sequences
lcp 2: add ("ab", 0, 2)
lcp 2: dont add ("ba", 1, 2) because it intersects with ("ab", 0, 2)
lcp 2: add ("ab", 6, 2)
lcp 1: no sequences
collection = [("ab", 0, 2), ("ab", 6, 2)]
(order by position not by which one was added first)
<STEP 6>
recreate input by iterating through the collection in order and
filling in gaps with the normal input:
input = "ab"*2 + input[4..5] + "ab"*2 + input[10..10]
埃夫根尼，如果你再次看到这个问题，我想问你一个简单的问题：
我做的第五步正确吗？也就是说，我是否根据生成它们的LCP组添加序列（首先是LCP值较高的组）或者是跟LCP有什么关系？
另外，如果第4步或第6步有任何问题，请告诉我，但对于这个例子来说，我所做的似乎非常有效。
最佳答案
我必须澄清原始答案中“按LCP值分组”的含义。事实上，对于具有选定LCP值的组，我们应该包括具有较大LCP值的所有条目。
这意味着对于您的示例，在处理lcp3时，我们需要将前面的条目0和6合并到此组。在处理lcp2时，我们需要将前面的所有条目与lcp3和lcp4合并：0、1、2、6、7。
结果，两（ab）对和一（ba）对在滤波后仍然存在。但由于（ba）与第一（ab）对“相交”，因此在步骤5中被拒绝。
另外，他说在第4步的末尾，我们应该有文本中所有可能的序列，他是说所有可能的重复序列吗？
对，我是说所有可能的重复序列。
这是一个已知的算法，它的名字我可以在其他地方找到更多的细节吗？
我不知道以前从未见过这样的算法。
下面是步骤2。4可以实现（伪代码）：
for (in_sa, in_src) in suffix_array: # step 2
lcp_groups[max(LCP[in_sa.left], LCP[in_sa.right])].append((in_sa, in_src))
apply(sort_by_position_in_src, lcp_groups) # step 3
for lcp from largest downto 1: # step 4
# sorted by position in src array and unique:
positions = merge_and_uniq(positions, lcp_groups[lcp])
for start in positions:
pos = start
while (next = positions[pos.in_src + lcp]).exists
and LCP.RMQ(pos.in_sa, next.in_sa) >= lcp
and not(prev = positions[pos.in_src - lcp]).exists # to process each
and LCP.RMQ(pos.in_sa, prev.in_sa) >= lcp): # chain only once
pos = next
if pos != start:
pass_to_step5(start, lcp, pos + lcp)
在这里，我没有为
positions计划任何特定的数据结构。但为了方便起见，我们假设了一个有序关联数组。rmq是范围最小查询，因此lcp数组应该进行相应的预处理。这段代码实际上与op中的代码相同，但它没有使用昂贵的字符串比较（比如
common != prefix(input, pos+lcp*i, lcp)），而是使用rmq，如果正确实现了rmq，它几乎可以立即工作（并且具有与字符串比较相同的效果，因为它允许在与前面的子字符串相同的起始字符太少时拒绝子字符串）。它具有二次最坏情况下的时间复杂度。对于像“aaaaaaaa”这样的输入数组应该很慢。发现“更好”字符串的时间复杂度是不容易的，在“平均”情况下可能是次二次。同样的问题可以用更简单的二次时间算法来解决：
def loop_rolling(begin, end):
distance = (end - begin) / 2)
for d from distance downto 1:
start = pos = begin
while pos + d < end:
while (pos + d < end) and (src[pos] == src[pos + d]):
++pos
repeats = floor((pos - start) / d)
if repeats > 0:
pass_to_step5(start, d, start + d * (repeats + 1))
start = pos
或者可以通过删除步骤5和6使其变得更简单但是下面的变体有一个缺点。它太贪心了，所以它会找到2*（2*（ab））ab而不是5*（ab）：
def loop_rolling(begin, end, distance):
distance = min(distance, (end - begin) / 2))
for d from distance downto 1:
start = pos = begin
while pos + d < end:
while (pos + d < end) and (src[pos] == src[pos + d]):
++pos
repeats = floor((pos - start) / d)
if repeats > 0:
loop_rolling(begin, start, d - 1)
print repeats+1, "*("
loop_rolling(start, start + d, d - 1) # "nested loops"
print ')'
loop_rolling(start + d * (repeats + 1), end, d)
return
else:
if d == 1: print src[start .. pos]
start = pos