我在面试中遇到了一个有趣的问题，但我无法回答它，也没有在Google上找到答案。
问题如下：
你获得了一个数据流。通过变量声明，你如何找出数据中是否存在重复或循环。
数据流的示例如下：
100100100100
0001000100010001
100100010001
10...0010....010....01(where 0....0 is 0^10^10^10)
这个问题该如何解决？有没有针对这种问题的算法？
如何在数据流中找到循环/重复？
4
这个问题该如何解决？有没有针对这种问题的算法？
- Indzi
2个回答
5
我认为解决这个问题有两种方法：
1. 最长重复子串问题
这是一个广为人知的问题，可以在线性时间内解决。您需要为字符串构建后缀树，然后对其进行分析。
请参考此文章了解详情。
2. 重复子串问题（任意）
您可以修改“最长重复子串”算法以查找任何重复的子串。
- Gor
3
它可以用于字符串，但我很好奇，它可以用于流吗？ - Fallen
如果您可以等待流结束，您可以使用此算法处理整个流数据。如果您必须在流中动态执行此操作，我认为您可以修改前缀树构建算法，然后动态添加新元素，并在每次新数据到达流时进行检查。 - Gor
@ Gor确定，一切都是可以修改的，但是你所提到的算法并不太适合描述的问题... - Andriy Berestovskyy
3
一种简单粗暴的解决方案是使用map或dictionary，例如对于流100100100100，它将是:
dict["1"]++
dict["10"]++
dict["100"]++
dict["1001"]++
我们需要重复查找直到最大长度。然后我们删除第一个符号并重复，即删除1，分析剩下的00100100100：
dict["0"]++
dict["00"]++
dict["001"]++
dict["0010"]++
最后，我们遍历map，并打印所有具有多个值的键。
虽然还有更高效的算法，但我认为这是最简单的。
- Andriy Berestovskyy
2
@Fallen 为什么不呢，我们只需要一个缓冲区大小
max_len_of_repetition_to_find，它将作为一个滑动窗口... - Andriy Berestovskyy是的，它将使用一个额外的参数，如 max_len_of_repetition_to_find。但我很好奇，因为OP并没有提到有任何这样的参数给定。 - Fallen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接