Równoważność cykliczna dwóch słów

Dwa słowa są równoważne cyklicznie, gdy jedno z tych słów można przesunąć cyklicznie w taki sposób, aby uzyskać drugie słowo. Na przykład słowa

 u = aaabab
 v = abaaab

są równoważne cyklicznie (wystarczy pierwsze przesunąć cyklicznie o 4 znaki w lewo):

 0 : aaabab  =  u
 1 : aababa
 2 : ababaa
 3 : babaaa
 4 : abaaab  =  v
 w = abaaab

Sprawdzenie czy słowa u i v są równoważne cyklicznie można sprowadzić do problemu wyszukania wzorca u w tekscie vv (słowo v połączone ze samym sobą). Można to zrobić np. za pomoca algorytmu KMP.

Tutaj jednak przedstawimy znacznie prostszy algorytm, działający w czasie liniowym O(n) i nie wymagający żadnej dodatkowej pamięci. W algorytmie KMP potrzebna jest bowiem dodatkowa pamięć na tablicę funkcji prefiksowej Knutha.

bool equiv_cyc(const string &u, const string &v)
{
  int n = u.length(), i = -1, j = -1, k;
  if (n != v.length()) return false;
 
  while( i<n-1 && j<n-1 )
  {
    k = 1;
    while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
    if (k>n) return true;
    if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
  }
  return false;
}