Rozwiazanie Z Uzyciem Kmp

Aby sprawdzić czy dane dwa słowa v i u są równoważne cyklicznie tj. sprawdzic czy da się tak przestawić jedno z nich aby uzyskac drugie, wystarczy wyszukać wzorzec u w podwojonym slowie v tj. takim, że jego konce są złączone ze soba (jest to inaczej mówiąc słowo vv). Można to zrobić np. algorytmem Knutha-Morrisa-Pratta. Przykładowo mając dane słowo v - ALAMAKOTA i u - OTAALAMAK, aby sprawdzic czy sa one rownoważne cykliczne szukamy wystąpien slowa OTAALAMAK w slowie ALAMAKOTAALAMAKOTA. Jak widać można znaleźć takie wystąpienie na pozycji 6 w slowie vv.

wczytaj slowa u i v

if(u.length != v.length) //nie sa rownowazne cyklicznie

v = v + v; //podwajamy slowo v

szukaj pierwszego wystapienia wzorca u w slowie v (teraz bedacym vv)

if(znaleziono) //sa rownowazne cyklicznie

else //nie sa rownowazne cyklicznie
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License