401. Палиндромы

 

Обыкновенный палиндром – это строка символов, которая одинаково читается как слева направо, так и справа налево.

Строка называется зеркальной, если после замены всех ее символов на зеркальные отображения, она будет читаться с конца так же, как и исходная строка. Зеркальные буквы поданы в таблице ниже. Например, строка "3AIAE" является зеркальной. Если строка содержит букву, которая не имеет зеркального отображения, то такая строка не может быть зеркальной.

Зеркальный палиндром – это строка символов, которая одновременно является обыкновенным палиндромом и зеркальной строкой. Например, строка "ATOYOTA" является зеркальным палиндромом.

 

символ

зеркальное

отображение

символ

зеркальное

отображение

символ

зеркальное

отображение

A

A

M

M

Y

Y

B

 

N

 

Z

5

C

 

O

O

1

1

D

 

P

 

2

S

E

3

Q

 

3

E

F

 

R

 

4

 

G

 

S

2

5

Z

H

H

T

T

6

 

I

I

U

U

7

 

J

L

V

V

8

8

K

 

W

W

9

 

L

J

X

X

 

 

 

Вход. Состоит из нескольких строк, каждая из которых содержит до 20 символов.

 

Выход. Для каждой входной строки вывести ее и сообщение о том, чем она является в соответствии со следующей таблицей:

 

строка вывода

критерий

" -- is not a palindrome."

не палиндром и не зеркальное отображение

" -- is a regular palindrome."

палиндром, но не зеркальное отображение

" -- is a mirrored string."

не палиндром, но зеркальное отображение

" -- is a mirrored palindrome."

палиндром и зеркальное отображение

 

После каждой строки вывода печатать пустую строку.

 

Пример входа

NOTAPALINDROME

ISAPALINILAPASI

2A3MEAS

ATOYOTA

 

Пример выхода

NOTAPALINDROME -- is not a palindrome.

 

ISAPALINILAPASI -- is a regular palindrome.

 

2A3MEAS -- is a mirrored string.

 

ATOYOTA -- is a mirrored palindrome.

 

 

РЕШЕНИЕ

обработка строк

 

Анализ алгоритма

Задача решается напрямую. Следует проверить, является ли входная строка палиндромом и зеркальной согласно их определениям.

 

Реализация алгоритма

Строка mirrors содержит зеркальные отображения букв. Массив messages содержит выводимые сообщения. Массив s содержит тестируемую строку.

 

                 /*ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789*/

char  mirrors[36]="A   3  HIL JM O   2TUVWXY51SE Z  8 ";

char  messages[4][30] = {

" -- is not a palindrome.",

" -- is a regular palindrome.",

" -- is a mirrored string.",

" -- is a mirrored palindrome." };

char s[21];

 

Функция get_mirror возвращает зеркальное отображение символа c. Если символ c не имеет зеркального отображения, то функция возвращает пробел ‘ ‘.

 

char get_mirror(char c)

{

  return mirrors[((c >= '1') && (c <= '9')) ? (c - '1' + 26) : (c - 'A')];

}

 

Функция check_string возвращает номер сообщения result, которому удовлетворяет входная строка.

 

int check_string()

{

  int result;

  char *p, *q;

 

Изначально считаем, что входная строка является зеркальным палиндромом, присвоим переменной result значение 3. Переменная p указывает на начало строки, q – на конец строки. Пока указатель p находится левее q,  двигаем p на одну позицию вправо, а q – на одну позицию влево. Каждый раз проверяем символы *p и *q на равенство. Если они не равны, то строка s не является палиндромом. Если *p не равно зеркальному отображению буквы *q, то строка s не является зеркальной.

 

  result = 3;

  p = s;

  q = s + strlen(s) - 1;

  while((p <= q) && result)

  {   

    if (*p != *q) result &= ~1;

    if (*p != get_mirror(*q)) result &= ~2;

    p++; q--;

  }

  return result;

}

 

Основной цикл программы. Заносим входную строку в массив s и печатаем нужное сообщение.

 

while(scanf("%s",s) == 1)

  printf("%s%s\n\n", s, messages[check_string()]);