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.
Dla przykładu, słowa
ababa i
aaaab są prawie cyklicznie
równoważne, a słowa
ababa i
bbbbb nie są.
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
Dla danych wejściowych:
5
ababa
aaaab
poprawną odpowiedzią jest:
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.