Палиндром — это такие слова, числа или символы, которые читаются одинаково в обоих направлениях. Палиндромы бывают образованы одним словом, состоящим из 1-2 символов, а могут быть образованы целыми текстами. Пример палиндрома из одного слова:
О! — восклицание удивления;
11;
дед;
Анна;
казак;
123321;
и др.
Пример палиндрома из нескольких слов:
«А роза упала на лапу Азора»;
«Аргентина манит негра»;
«Лёша в полке клопа нашёл»;
«Нажал кабан на баклажан»;
«Ешь немытого ты меньше»;
и др.
Самый длинный палиндром на русском языке на сегодня — роман-амор «Зори Роз» или «Фантастический сон на берегу реки за минуту до пробуждения». Вот характеристика этого палиндрома:
строгий стиль, где допущена только замена символа «е» и «ё»;
соблюдает точный размер и рифму;
содержит 20836 букв;
содержит 5638 слов;
содержит 1206 палиндромных пар.
Причем тут программирование? — спросите вы.
Палиндром в программировании
На самом деле, в обычной жизни редко когда есть нужда специально искать палиндром в тексте, а в программировании еще реже, чем в обычной жизни. Основная сфера, где палиндром и программирование пересекаются, — это конкурсное программирование и собеседования. И там и там задач по поиску палиндрома в текстах хватает. Другое практическое применение поиска палиндрома в программировании остается на индивидуальном уровне, то есть, возможно, кому-то это надо, но чаще всего вообще никому не нужно. Суть сегодняшней статьи заключается в том, чтобы показать способ, как правильно выстроить алгоритм, который выполнит поиск палиндрома в тексте. Потом эти знания вы сможете применять по своему усмотрению.
Палиндром и С/С++
На одном только языке программирования С/С++ можно использовать несколько подходов для написания алгоритма поиска палиндрома, например:
простой алгоритм с применением асимптотики;
метод с использованием хеша;
алгоритм Манакера;
палиндромное дерево;
и др.
Программный скрипт, определяющий слово-палиндром и написанный на языке Си/С ++:
#include <iostream>
#include <cstring>
using namespace std;
bool check_polindrom(string word)
{
int len = word.length();
for(int i = 0; i< len/2; ++i)
{
if(word[i] != word[len-i-1])
{
return false;
}
}
return true;
}
int main()
{
string str;
cout<< "Введите символы: ";
cin >> str;
if(check_polindrom(str))
{
cout<< "Эти символьные знаки являются палиндром.";
}
else
{
cout<< "Эти символьные знаки не принадлежат к палиндрому";
}
return 0;
}
Скрипт программы на Си/С++, определяющий палиндром в документе:
void SlowN2::oddCount()
{
for(int indMiddle = 0; indMiddle< str.length(); ++indMiddle)
{
int leftLimit= indMiddle - 1, rightLimit = indMiddle + 1;
while(leftLimit >= 0 && rightLimit< str.length() && str[leftLimit] == str[rightLimit])
{
++cntPalindromes;
--leftLimit;
++rightLimit;
}
}
}
void SlowN2::evenCount()
{
for(int indMiddle = 0; indMiddle< str.length(); ++indMiddle)
{
int leftLimit = indMiddle, rightLimit = indMiddle + 1;
while(leftLimit >= 0 && rightLimit< str.length() && str[leftLimit] == str[rightLimit])
{
++cntPalindromes;
--leftLimit;
++rightLimit;
}
}
}
Палиндром и Python
Отыскать палиндром в документе, используя Python, несложно. Алгоритм поиска выглядит следующим образом:
необходимо прочитать символьный набор;
сохранить символьный набор в переменной;
«перевернуть» набор символов;
сравнить оригинальный набор с «перевернутым»;
если наборы совпадают, тогда необходимо вывести, что символы являются палиндромом;
если наборы не совпадают, тогда необходимо вывести оповещение об этом.
Пример кода:
str = ' строка, которую необходимо проверить на палиндромность'
str = str.casefold()
rev = reversed(str)
if list(str) == list(rev):
print("Это палиндром!")
else:
print("Это не палиндром!")
Палиндром и PHP
Чтобы найти палиндром, применяя PHP, необходимо преследовать ту же логику при составлении программы, как и на Python.
Как выглядит код программы:
<_?php
// для того чтобы определить палиндром в php, необходимо составить специальную функцию
$input = "строка, которую необходимо проверить на палиндромность";
echo '
Input String '. $input;
//реверсируем («переворачиваем») строку
$reverse = strrev($input);
echo '
Ouput String '. $reverse;
//сравниваем, если оригинальная строка одинакова с «перевернутой»
if($input == $reverse) (
echo '
'.$input.' Это палиндром!';
)
else (
echo '
'.$input.' Это не палиндром!';
)
?>
Заключение
Палиндром можно определить, применяя возможности любого языка программирования, а не только C/C++, Python, PHP. Для того чтобы найти палиндром, необходимо осознать механизм, по которому нужно осуществлять поиск. Реверс наборов символов (строк) — это самый простой подход, который в большинстве случаев помогает.
Другое
