Best algorithm to determine whether two arrays can be the same in a circular queue

Question

I'm trying to figure out an efficient way to determine whether two distinct arrays of the same size can be shifted to form the same circular queue. For example:

Array1 = ['A','B','C','D']
Array2 = ['D','A','B','C']

Can form the same circle if both ends are joined together:

I thought that one way would be to loop through one of the arrays while one remains constant, for example:

while Array1 is not = Array2 and iterations < Length of Array1
      temporary = Array1[last]
      for index is 0, add 1, before index = last
           temporary[index] becomes temporary[index+1]
      Array1[0] = temporary
      if Array1 == Array2 return TRUE
return FALSE

Is there a more efficient way? I would need to do this check for several arrays among each other and remove duplicates. Plain speech, pseudocode or Python/C# data structures/code would be appreciated.

Answer 1

Once we've asserted that both arrays have the same length, we can duplicate one array, and the problem is reduced to the substring search problem "ABCD" in "DABCDABC". There are a variety of algorithms available for that. Note that unless the data can be mapped to simple strings, manually implementing the chosen algorithm would be better. In this case, you would not physically duplicate the array but rather use index mod length for accessing items.

Answer 2

Obviously you can check every possible offset between the two arrays and check every element for equality. But that always takes quadratic time. It's better to take the first element of Array1 and skip through Array2 until you find that same value. You save yourself lots of comparisons that can't possibly succeed because you already know the arrays won't be identical. (You might even find the rarest element in Array1 somehow and start with that, since it's even more likely to save you work.)

How much work this saves depends on how long the arrays are and how many identical values are in them, but in practice it could be a great part of the total effort.

Answer 3

This is what I came up with in C#:

static bool AreArraysCircular(char[] Array1, char[] Array2) 
    {
        bool flag = false;
        if (Array1.Length != Array2.Length) return flag; //check the length, if not the same means the arrays are not circular
        int len = Array1.Length;
        int matches = 0; //count for matching characters
        for (int i = 0; i < len * 2; i++)
        {
            if (Array1[matches] == Array2[i % len])
            {
                matches++; //find the next match
                if (matches == len) //already matched whole array
                {
                    flag = true;
                    break;
                }
            }
            else matches = 0; //safeguard probably unnecessary
        }
        return flag;
    }

EDIT: Algorithm firstly checks the lengths of both arrays, then it goes through loop double the length of arrays and with index mod length accesses the element in second array and waits for the match. This is using the proposed substring search problem solving.