Узнать номер символа, который нужно удалить чтобы строка стала палиндромом

29 сентября 2021, 12:50

Накопал в интернете разные коды на C++:

#include <iostream>
#include <algorithm>
#include <array>
#include <string>
std::string palindrome(const std::string& s) {
    if (s.size() == 0 || s.size() == 1) {
        return s;
    }
    if (s.front() == s.back()) {
        return s.front() + palindrome(s.substr(1, s.size() - 2)) + s.back();
    }
    std::array<std::string, 3> branches; 
    branches[0] = palindrome(s.substr(1));
    branches[1] = palindrome(s.substr(0, s.size() - 1));
    branches[2] = palindrome(s.substr(1, s.size() - 2));
    return *std::max_element(branches.begin(), branches.end(), []
        (const std::string& a, const std::string& b) {
            return a.size() < b.size();
        });
}
int main()
{
    std::string target{ "12343271" };
    std::cout << palindrome(target) << std::endl;
}

Программа работает, но выводит палиндром - готовый, а должно быть число... Подскажите как исправить программу

Answer 1

Не ожидал что задача вызовет сложности. Решение за линейно.

bool ok(const char* l, const char* r){
    while (l < r){
        if (*l != *r)
            return false;
        l++;
        r--;
    }
    return true;
}
int getPosition(const char *inp){
    const char* l = inp;
    const char* r = inp;
    while (*r) r++;
    r--;
    while (l < r){
        if (*l == *r)l++,r--;
        else if (ok(l+1,r))
            return l-inp+1;
        else if (ok(l,r-1))
            return r-inp+1;
        else return -1;
    }
    return 0;
}

Запускаемый пример https://ideone.com/ngfBi6

Answer 2

Обращаю внимание на то, что задача взята из школьного этапа всероссийской олимпиады школьников по информатике, которая идёт сейчас, поэтому помогать автору вопроса в несамостоятельном выполнении соревновательного задания не есть здорово.

С уважением, председатель региональной предметно-методической комиссии всероссийской олимпиады школьников по информатике в г. Москве

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Инициализация статических объектов в С++

Пусть есть программа:

115

c++

C++, volatile и strict aliasing rules

Подскажите, пожалуйста, законно ли использование спецификатора volatile для локального обхода требований строгих псевдонимов?

211

c++

Логирование в консоль Catch2

Почему Catch2 не логирует сообщения? В пустом TEST_CASE пишу INFO("42");После запуска в консоли получаю:

173

javascript

SVG маска и анимация при наведении

Я не очень хорошо знаком с SVG и маской, и я хотел бы знать, возможно ли, чтобы анимация, как на картинке, была бы при наведении мыши? (с JQuery или...