How to find loop/ repetition in a data stream?

Question

I came across an interesting question in an interview. But I couldn't answer it, neither I found it on Google.

Question is as follows:

You are given a data stream. With the help of variable declaration how you can find whether there is any repetition or loop in the data.

Example of the data stream are:

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

How can this problem be solved? Is there any algorithm for such kind of problem?

Answer 1

I think there must two approaches to this problem

1. Longest repeated substring problem

This is well known problem which have solution in linear time. You have to construct suffix tree for your string then analyze it. Please check this article for details

2. Repeated substring problem (any)

You can modify Longest repeated substring to find any repeated substring.