Задано некоторое предложение на неизвестном языке. Назовем слово в нем чемпионом, если оно является палиндромом и количество букв в нем максимально. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложении нет.
Задача взята с сайта e-olymp.
Входные данные
Предложение на неизвестном языке.
Выходные данные
Номер слова-чемпиона.
Тесты
| Предложение | Номер слова-чемпиона |
| Oo, it aaa is not bb. | 3 |
| Tummut, suuruu 18! | 1 |
| Qrtew asd x, pol 123 xcv. | 3 |
| Antaa, qor — aapapaa for Saippuakivikauppias kappak! | 6 |
| A b C d E f G h | 1 |
| NoPalindrome | 0 |
| 123321 oro 1234554321? | 3 |
Примечание : в ходе решения задачи выяснилось, что, если в предложении присутствуют несколько палиндромов одинаковой длины, следует вывести первый из встретившихся.
Алгоритм
В данной задаче требуется найти в заданном предложении палиндром максимальной длины. Так как нам нужно проводить анализ отдельных слов, то считывать будем по одному слову пока предложение не закончится, при этом храня порядковый номер текущего слова. Однако, следует учесть следующее:
- Слово-палиндром может содержать в себе буквы различного регистра, что может помешать при проверке на палиндромность. Во избежание ошибки переведем все слово, например, в нижний регистр с помощью соответствующей функции.
- В предложении встречаются знаки препинания, поэтому если последний символ в слове не является буквой латинского алфавита или цифрой (проверку для удобства чтения вынесем в отдельную функцию), заменим его на нуль-символ, чтобы в дальнейшем его не учитывать.
После проведенных операций найдем длину текущего слова и, если она превышает максимальную длину ранее найденного слова-чемпиона, проверим, является ли текущее слово палиндромом. Осуществим это с помощью рекурсивной функции, сравнивающей соответствующие символы в данной строке по индексам. Функция работает до тех пор, пока начальный и конечный индекс не сравняются или поменяются местами (изначально первый индекс (start) равен нулю, а конечный (end) меньше длины строки на единицу), или же соответствующие символы окажутся разными. Если данное слово оказалось палиндромом, храним его порядковый номер в предложении.
Как только предложение завершено, выводим индекс найденного слова-чемпиона, или индекс первого из них, если таковых было несколько.
Код программы:
|
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 |
#include <iostream> #include <cstring> using namespace std; const int registerShift = 'A' - 'a'; // Сдвиг от верхнего регистра к нижнему по таблице ASCII // Функция, для определения, является ли текущий символ "буквой" в контексте данной задачи bool IsAllowedSymbol(char symbol) { return ((symbol >= '1' && symbol <= '9') || (symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z')) ? true : false; } // Функция, для определения, является ли текущее слово палиндромом bool IsPalindrom(char *word, int begin, int end) { return (end <= begin) ? true : (word[begin] != word[end]) ? false : IsPalindrom(word, ++begin, --end); } // Функция, которая переводит все слово в нижний регистр void ToLowerCase(char *word) { for (int i = 0; i < strlen(word); i++) { if (word[i] >= 'A' && word[i] <= 'Z') word[i] -= registerShift; } } int main() { char word[1001]; int wordSize, maxSize = 0, indexOfPalindrom = 0; for (int i = 1; cin >> word; i++) { ToLowerCase(word); // Перевод слова в нижний регистр if (!IsAllowedSymbol(word[strlen(word) - 1])) word[strlen(word) - 1] = '\0'; // Не учитывать последний символ слова, если это не "буква" (т. е. знак препинания) wordSize = strlen(word); if (wordSize > maxSize) { if (IsPalindrom(word, 0, wordSize - 1)) { maxSize = wordSize; indexOfPalindrom = i; } // Храним новый максимум и индекс текущего наибольшего палиндрома, если он был найден } } // Чтение по словам до конца предложения cout << indexOfPalindrom; return 0; } |
Мне понравилась Ваша рекурсивная функция проверки на палиндром.
Зачтено.
Почему вы в функции IsAllowedSymbol проверяете цифры от 1 до 9 а как же 0?