Prawie równoważne słowa [B]

Limit pamięci: 64 MB

W ścisłym sensie słowo prawie oznacza tyle, co nie. Z drugiej strony nie są to jednak synonimy, dokładniej słowo prawie jest bliższe słowu tak niż słowo nie.

Dwa słowa nazywamy cyklicznie równoważnymi, jeżeli w wyniku wykonania pewnej liczby operacji przesunięcia jednej litery z początku pierwszego słowa na jego koniec otrzymujemy słowo drugie. Dla przykładu, słowa ababa i abaab są równoważne cyklicznie, a słowa ababa i baaab nie są. Dwa słowa nazywamy prawie cyklicznie równoważnymi, jeżeli:

• nie są równoważne cyklicznie, ale
• w wyniku wykonania pewnej liczby operacji przesunięcia litery z początku pierwszego słowa na jego koniec otrzymujemy słowo, które w stosunku do drugiego słowa różni się tylko na jednej pozycji.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia dwa słowa,
• sprawdzi czy są one prawie cyklicznie równoważne, a jeżeli tak, to ten fakt udowodni,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca długość każdego ze słów. Drugi wiersz wejścia zawiera pierwsze słowo, trzeci zaś - drugie. Każde słowo jest ciągiem małych liter alfabetu angielskiego.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedno słowo - TAK jeżeli słowa są prawie cyklicznie równoważne, a NIE w przeciwnym przypadku. Jeżeli pierwszy wiersz wyjścia zawierał słowo TAK, to drugi wiersz powinien zawierać rosnący ciąg liczb całkowitych nieujemnych z zakresu od do , pooddzielanych pojedynczymi odstępami. Ciąg na wyjściu powinien zawierać wszystkie możliwe liczby ruchów przesunięcia litery z początku na koniec pierwszego słowa, po których w rezultacie otrzymujemy słowo, różniące się na dokładnie jednej pozycji do słowa drugiego.

Przykład

5
ababa
aaaab

TAK
2 4

gdyż po przesunięciu o 2 literki pierwsze słowo staje się słowem abaab, a o 4 literki - słowem aabab,

natomiast dla danych:

5
ababa
bbbbb

poprawnym wynikiem jest:

NIE

Autor zadania: Jakub Radoszewski.