Równoważność cykliczna ciągów.

0

Mam problem z tym kodem(nie należy do mnie http://www.rafalnowak.pl/wiki[...]zna_dw%C3%B3ch_s%C5%82%C3%B3w)

no bo dla np.:
u = 123
v = 321
Czy z tym kodem jest wszystko ok?
Funkcja się nie kończy bo k będzie zawsze równe 1?
u jest przesuwane czy v ?
Straszny mam w końcu mętlik, proszę o pomoc.

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;
} 
1

http://rextester.com/PTUDUQ59894

k:1 i:-1 j:-1 n:3
k:1 i:-1 j:0 n:3
k:2 i:-1 j:1 n:3
false: k:2 i:-1 j:3 n:3
0

funkcja kończy się, nieprawdziwy staje się warunek w linii 12 "j<n-1" dla j = 3, n = 3
j rośnie, i nie zmienia się czyli przsuwany jest v

0

A wiesz jak poprawić ten algorytm?

0

naiwna implementacja:

bool equiv_cyc(const string &u, const string &v)
{
     if (u.size()!= v.size())
          return false;
     if (u.empty())
          return true;
     string x = u;
     size_t n = x.size()-1;
     while (x != v && n>0)
     {
          std::rotate(x.begin(), x.begin()+1, x.end());
          --n;
     }
     return x == v;
}

naiwna implementacja bez kopiowania:

bool equiv_cyc(const string &u, const string &v)
{
    if (u.size()!= v.size())
        return false;
    if (u.empty())
        return true;
    string x = u;
    size_t n = x.size();
    for (size_t i=0; i<n; ++i)
    {
        if (std::equal(u.begin(), u.end()-i, v.begin()+i, v.end())
            &&std::equal(u.end()-i, u.end(), v.begin(), v.begin()+i))
            return true;
    }
    return false;
}

http://ideone.com/mSiIoO

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0