Cyklicznie równoważne sufiksy danych słów

Question

Załóżmy, że mamy sobie słowa A i B, oba o długości n. Naszym zadaniem jest odpowiedzieć na zapytanie, czy są w nich takie podsłowa (koniecznie sufiksy, słowa wyjściowe też są podsłowami), że są one sobie cyklicznie równoważne. Przy czym zakładamy, że cyklicznie równoważne są takie słowa W1, W2, że W1 = XY a W2 = YX, gdzie X i Y są to słowa niepuste. Jak byście to rozkminili? Zakładamy, że prefiksy do słów A i B są sobie równe (bardzo ważne).

Answer 1

Nie wiem czy dobrze zrozumiałem to zadanie ale z tego co wywnioskowałem to chyba będziesz potrzebował jakiegoś słownika(bazy słów). Z porównywaniem ciągu znaków nie ma większego  problemu ale sprawdzenie czy to jest logiczne słowo wymaga jakiejś bazy. Nie rozumiem tego porównania W1 = XY i W2 = YX. Czy oznacza ono, że przyrostek W1 to przedrostek W2? Co do kodu jeśli znasz długość przedrostka lub przyrostka (zakładające, że słowa, przyrostki i przedrostki tych słów maja równą długość znaków) to porównanie ciągu znaków nie jest zbyt skomplikowane, wystarczy sprawdzać literka po literce.

Comments

Szukam słów postaci XYZ i XZY, gdzie Y i Z są niepuste. Potrzebuję to mieć w złożoności szybszej niż O(n^2) gdzie n = liczba znaków w słowie, kwadratowe rozwiązanie posiadam.

---

Tak więc z tego co mówisz to:

W1 = W2 = n

W1 = XYZ i W2 = XZY

ZY = n – X

Przyjmijmy, że U to pierwsza litera po przedrostku X(czyli X + 1).

Po wykonaniu zmienna zm będzie zawierała długość Y.

int g = 0, j = 1, i = 0, zm = 1;
while(1)
    {
        if(j + U +1 == strlen(w2))
        {
            break;
        }
        if(w1[U+g] == w2[U+j])
        {

            for(i = U+j+1 ; i < strlen(w2); i++)
            {
                g++;
                if(w1[U+g] == w2[i])
                {
                    zm++;
                    if(i +1 == strlen(w2))
                        break;
                }
                else
                {
                    g = 0;
                    zm = 1;
                    j++;
                    break;
                }
            }
        }
        else
        {
            j++;
        }
    }

Kod nie jest doskonały, zadziała nawet dla nielogicznych słów, ale mam nadzieję, że pomogłem.