Условие
Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!
На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.
Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.
Тесты
Входные данные Выходные данные
| array | yes |
| iliya | no |
| anna | yes |
| cbaabcb | yes |
| arrya | no |
| anana | yes |
| bcdcbaa | yes |
Код программы №1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <string> using namespace std; bool palindrome (string const *s) { for (int i = 0; i < (*s).size() / 2; ++i) { if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false; } return true; } int main() { string s; cin >> s; for (int i = 0; i <= s.length(); i++) { s += s[0]; s.erase(s.begin()); if (palindrome(&s)) { cout << "yes"; return 0; } } cout << "no"; return 0; } |
Решение №1
Проверять, является ли входное слово «затаившимся палиндромом» можно непосредственно перенося буквы из начала в конец и каждый раз проверяя, не стало ли слово палиндромом. Для удобства можно написать отдельную функцию, которая будет проверять, является ли слово палиндромом.
Код программы №2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <vector> using namespace std; int main() { string s; cin >> s; int n = s.length(); //дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки s += s; const int p = 31; vector <long long> p_pow (2*n); //вектор степеней числа p p_pow[0] = 1; for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1]; long long P1 = 0, P2 = 0; for (int i = 0; i < n; ++i) { P1 += (s[i] - 'a' + 1) * p_pow[i]; P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i]; } if (P1 == P2) { bool check = true; for (int i = 0; i < n; ++i) if (s[i] != s[n - i - 1]) check = false; if (check) { cout << "yes"; return 0; } } for (int i = 0; i < n; ++i) { P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i]; P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1]; if (P1 == P2) { bool check = true; for (int j = i + 1; j < i + 1 + n; ++j) if (s[j] != s[2*i + 1 + n - j]) check = false; if (check) { cout << "yes"; return 0; } } } cout << "no"; return 0; } |
Решение №2
Для решения задачи можно воспользоваться техникой хеширования строк. Изначально продублируем строку, поскольку тогда все циклические перестановки исходной строки будут подстроками длины $n$ продублированной строки, где $n$ — длина исходной строки.
Можно сначала сравнить хеши исходного слова и «перевернутого» к нему. Далее будем строить значения полиномиальных хешей, умноженных на $p$ в соответствующей степени, всех следующих подстрок длины $n$ и «перевернутых» к ним.
Заметим, что вычислять значение хеша «перевернутой» строки можно без её копирования, поскольку отличается она от «прямой строки только тем, что степени числа $p$ умножаются на преобразованые коды соответствующих символов строки в обратном порядке. Поэтому для вычисления хеша следующей «перевернутой» подстроки надо вычесть из предыдущего значения элемент с наибольшей степенью числа $p$, домножить полученное значение на $ p^2 $, т.к. мы, с одной стороны, решили смещать края подстроки, для которой мы проверяем на палиндром, умножая её хеш на соответствующую степень числа $p$, а с другой — текущая предпоследняя степень должна стать последней (из-за того, что рассматривается перевёрнутая подстрока и новый символ к ней присоединяется «в начало»).
Далее остается проверить, действительно ли подстрока, хеш которой равен хешу «перевернутой» подстроки, является палиндромом, чтобы избежать коллизии, когда двум разным строкам соответствуют равные хеши.
Но решение без этой проверки тоже удовлетворяет тесты на олимпиаде.
Код программы №3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <vector> using namespace std; int main() { string s; cin >> s; int n = s.length(); s += s; int len = s.length(); vector <int> d (len); int l = 0, r = -1; if (n % 2) { for (int i = 0; i < len; ++i) { d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1); while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]]) d[i]++; if (i + d[i] - 1 > r) { r = i + d[i] - 1; l = i - d[i] + 1; } if (r - l + 1 >= n) { cout << "yes"; return 0; } } } else { for (int i = 0; i < len; ++i) { d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1); while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]]) d[i]++; if (i + d[i] - 1 > r) { r = i + d[i] - 1; l = i - d[i]; } if (r - l >= n) { cout << "yes"; return 0; } } } cout << "no"; return 0; } |
Решение №3
Для решения задачи можно воспользоваться алгоритмом Манакера. Алгоритм позволяет находить все подпалиндромы строки, поэтому мы снова продублируем строку и будем искать в ней подпалиндром, длина которого равна длине $n$ исходной строки. Заметим, что нам достаточно проверять подпалиндомы, четность длины которых совпадает с четностью $n$. Далее будем сравнивать расстояние между концами $l$ и $r$ текущего палиндрома с $n$ (расстояние между концами может быть и больше $n$, т.к. мы уже определили, что четность этих величин будет совпадать, а если в строке найден подпалиндром длиной $s$, то существуют подпалиндромы и длиной $s-2$, $s-4$, … ).
Решение №1 задачи на ideone.com
Решение №2 задачи на ideone.com
Решение №3 задачи на ideone.com
Ссылка на контест