2

我的理解是龟兔式算法适用于迭代序列,也就是说,对于任何 x,succ(x) = x0。

我想实现一种算法,可以检测确定性和非确定性无限重复序列中的循环。

序列可能具有不重复的前缀子序列,例如在序列中1666666...,具有前缀1和重复模式6

该算法将返回序列中最长的重复模式。的重复模式001100110011...将是0011,的重复模式22583575837583758...将是58357

我的想法是从那里以某种方式生成可能的最长模式长度的猜测,但我无法按顺序排列。

4

1 回答 1

1

龟兔算法使用相同的地址来识别循环。这个问题需要一种不同的算法。某种形式的 trie 或结构(例如 LZW 压缩)将是我寻找解决方案的地方。

于 2015-09-07T19:26:47.170 回答