Find array that is repeating in other array

Let’s suppose that array B is made from array A by concatenating it with itself n times
(example: A=[1,2,3], n=3, B=[1,2,3,1,2,3,1,2,3])
What is an efficient algorithm to find A by given B (we don’t know n)?

>Solution :

Assuming that [1,2,1,2,1,2,1,2] means n is 4 and not 2, for example. In other words, you’re assuming the smallest such sublist, A. Otherwise, there could be multiple solutions.

1. Enumerate the unique integer divisors of the length of B (including 1). These would be the only valid candidates for n.

2. For each divisor, starting with the smallest, consider it as a candidate value for n:

   a. Take the first n elements of B and start checking whether it is a sublist that repeats through B (I’ll assume you can figure out an efficient way of doing this. I can add a suggestion if you need it.)

   b. If n works, then you’re done, otherwise, try the next divisor