如何在数据流中找到循环/重复？

Question

我在采访中遇到了一个有趣的问题.但是我无法回答它,也没有在Google上找到它.

问题如下:

您将获得一个数据流.在变量声明的帮助下,您可以如何查找数据中是否存在重复或循环.

数据流的示例是:

100100100100
0001000100010001
100100010001
10...0010....010....01(where 0....0 is 0^10^10^10)

怎样才能解决这个问题？是否存在针对此类问题的算法？

Answer 1

我认为这个问题必须有两种方法

1.最长的重复子串问题

这是众所周知的在线性时间内有解的问题.你必须suffix tree为你的字符串构造然后分析它.请查看此文章了解详细信息

2.重复子串问题(任何)

您可以修改Longest repeated substring以查找任何重复的子字符串.