Miglior algoritmo per determinare se due array possono essere uguali in una coda circolare

Una volta che abbiamo affermato che entrambi gli array hanno la stessa lunghezza, possiamo duplicare un array e il problema si riduce al problema di ricerca della sottostringa "ABCD" in "DABCDABC" . Per questo sono disponibili varietà di algoritmi . Si noti che, a meno che i dati non possano essere mappati su semplici stringhe, l'implementazione manuale dell'algoritmo scelto sarebbe migliore. In questo caso, non dovrai duplicare fisicamente la matrice ma piuttosto usare index mod length per accedere agli elementi.

Ovviamente è possibile controllare ogni offset possibile tra i due array e controllare ogni elemento per l'uguaglianza. Ma ciò richiede sempre un tempo quadratico. È meglio prendere il primo elemento di Array1 e saltare attraverso Array2 fino a trovare lo stesso valore . Ti risparmia molti confronti che non possono avere successo perché già conosci gli array non saranno identici. (Potresti anche trovare l'elemento più raro in Array1 in qualche modo e iniziare con quello, dal momento che è ancora più probabile che tu risparmi il tuo lavoro.)

Quanto lavoro risparmia dipende da quanto tempo sono gli array e quanti valori identici ci sono, ma in pratica potrebbe essere una grande parte dello sforzo totale.

Questo è ciò che mi è venuto in mente 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 controlla innanzitutto le lunghezze di entrambi gli array, quindi passa attraverso il doppio del loop della lunghezza degli array e con la lunghezza del mod dell'indice accede all'elemento nel secondo array e attende la corrispondenza. Questo sta usando la soluzione di problemi di ricerca della sottostringa proposta.