Неидеальный палиндром

10 Август 2019 - Время чтения: 16 минуты

Условие задачи: Дана строка символов длиной L, L <= 255. Выяснить, является ли строка палиндромом, и если нет, то можно ли сделать из неё палиндром, удалив какой-нибудь символ (на одной позиции). Если строка уже палиндром, программа должна вывести YES. Если из строки можно сделать палиндром, вывести позицию символа, который надо для этого удалить (позиции нумеруются с нуля). Если палиндром из строки получить невозможно - напечатать NO.

Примеры работы алгоритма:
abcba → YES
сabba → 0
abbca → 3
abaca → NO

Решение: Проверка на палиндром - одна из стандартнейших задач. Мы должны идти одновременно с начала до середины строки и с конца до середины, и проверять, совпадают ли символы - первый с последним, второй с предпоследним... В этой задаче нам нужно определить не только то, является ли строка палиндромом, но и на каком символе проверка ломается. Допустим, проверка сломалась на символе на позиции k. Значит, нам нужно исключить либо символ на позиции k, либо обратный ему L - k - 1. В первом случае нужно проверить часть строки, начиная с k + 1 и до L - k - 1, а во втором - с позиции k и до L - k - 2. В обоих случаях проверяемая подстрока имеет длину L - 2 * k - 1.


Программа на языке C99
#include <stdint.h>
#include <stdio.h>
#include <string.h>
 
#define N 255
 
size_t badpos(const char *const str, const size_t len)
{
    if (len > 1) {
        for (size_t i = 0; i < len / 2; ++i) {
            if (str[i] != str[len - i - 1]) return i;
        }
    }
    return SIZE_MAX;
}
 
int main(void)
{
    char str[N + 1];
    fgets(str, N + 1, stdin);
    size_t len = strlen(str);
    if (str[len - 1] == '\n') {
        str[--len] = '\0';
    }
    size_t k = badpos(str, len);
    if (k == SIZE_MAX) {
        printf("YES\n");
    } else {
        len -= 2 * k + 1;
        if (badpos(str + k + 1, len) == SIZE_MAX) {
            printf("%u\n", (unsigned)k);
        } else if (badpos(str + k, len) == SIZE_MAX) {
            printf("%u\n", (unsigned)(k + len));
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

Программа на языке Python
def badpos(s, i, j):
    while i < j:
        if s[i] != s[j]:
            return i
        i += 1
        j -= 1
    return None
 
s = input()
k = badpos(s, 0, len(s) - 1)
if k is None:
    print("YES")
elif badpos(s, k + 1, len(s) - k - 1) is None:
    print(k)
elif badpos(s, k, len(s) - k - 2) is None:
    print(len(s) - k - 1)
else:
    print("NO")

Работа со строками - это больное место программирования. Видимо, потому что изначально компьютеры задумывались как машины для научных расчётов. В каждом языке программирования свои особенности реализации этого типа данных. Приходится всё время перестраивать мышление. Это заметно даже по этим двум программам - они довольно разные.

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории