非迭代序列中的循环检测
Cycle detection in non-iterated sequence
我的理解是 tortoise-hare 类算法适用于迭代序列
也就是说，对于任何 x，succ(x) = x0.
我想实现一个算法，可以检测确定性和非确定性无限重复序列中的循环。
序列可能有一个非重复的前缀子序列，例如在序列1666666...中，有前缀1和重复模式6。
该算法将 return 序列中最长的重复模式。
001100110011... 的重复模式为 0011，22583575837583758... 的重复模式为 58357.
我的想法是以某种方式从那里生成对最长可能模式长度的猜测，但我无法按顺序进行。
tortoise-hare算法使用相同的地址来识别循环。这个问题需要一种不同的算法。某种形式的 trie 或结构，如 LZW 压缩，将是我寻找解决方案的地方。
我的理解是 tortoise-hare 类算法适用于迭代序列 也就是说，对于任何 x，succ(x) = x0.
我想实现一个算法，可以检测确定性和非确定性无限重复序列中的循环。
序列可能有一个非重复的前缀子序列，例如在序列1666666...中，有前缀1和重复模式6。
该算法将 return 序列中最长的重复模式。
001100110011... 的重复模式为 0011，22583575837583758... 的重复模式为 58357.
我的想法是以某种方式从那里生成对最长可能模式长度的猜测，但我无法按顺序进行。
tortoise-hare算法使用相同的地址来识别循环。这个问题需要一种不同的算法。某种形式的 trie 或结构，如 LZW 压缩，将是我寻找解决方案的地方。