Самый длинный код палиндрома (динамическое программирование c) завершается ошибкой с превышением времени ожидания для больших входных данных. Как это улучшить?

Question

Я учусь решать задачи динамического программирования c на LeetCode. Проблема в том, чтобы найти самый длинный палиндром в любой данной строке. Мой код хорошо работает для небольших входных строк. Но терпит неудачу для очень больших размеров входов. Ждем идей по его улучшению.

Код:

#include <iostream>
#include <vector>

class Solution {
    public:
    std::string longestPalindrome(std::string s) {
        std::vector<std::string> sequence;
        std::string dummy, longest;

        for(auto it = s.begin(); it < s.end(); it++){
            dummy += *it;
            for(auto  it2 = it+1; it2 < s.end(); it2++) {
                dummy += *it2;
                sequence.push_back(dummy);
            }
            dummy = "";
        }
        for(auto &item : sequence) {
            for(auto it = item.rbegin(); it < item.rend(); it++) {
                dummy += *it;
            }
            if(item == dummy && item.size() > longest.size()) {
                longest = item;
            }
            dummy = "";
        }
        if (longest.empty())
            longest += *s.begin();
        return longest;
    }
};

int main() {
Solution solver;
std::cout << solver.longestPalindrome("babadhabab") << std::endl;
return 0;
}

Answer 1

Я сделал некоторый код, и он работает хорошо, я думаю.
Я не уверен, что этот код идеален и быстр.
, но большая часть входных данных не является палиндромом, поэтому эта функция будет работать хорошо, Я полагаю (алгоритм) 1. итерируйте каждый символ и установите char в pivot 2. проверьте строку, является ли она палиндромом вокруг pivot 3. Большая часть входных данных не является палиндромом, поэтому это 4. WORST INPUT_DATA: все входные данные имеют одинаковое значение как 'aaaaaaaaaa'

    class Solution {
        public:
        std::string longestPalindrome(std::string const& input)
        {
            if (2 > input.length()) { return std::string(); }

            char const* input_data = input.c_str();
            int found_palindrome_max_len = 0;
            char const* found_palindrome = nullptr;
            char const* current = input_data+1;
            while ('\0' != *current)
            {
                auto palindrome = is_palindrome(input_data, current, found_palindrome_max_len);
                if (nullptr != palindrome) { found_palindrome = palindrome; }
                ++current;
            }

            if (nullptr == found_palindrome) { return std::string(); }
            return input.substr(found_palindrome - input_data, found_palindrome_max_len);
        }

        char const* is_palindrome(char const* begin, char const* pivot, int& max_palindrome_len)
        {
            std::cout << "[BEGIN] pivot=" << *pivot << ", max_len = " << max_palindrome_len << std::endl;
            bool is_odd_check = true; // ex) abcba (odd length)
            bool is_even_check = true; // ex) abccba (even lenth)
            int length = 1;
            char const* left = nullptr;
            char const* right = nullptr;
            char const* found = nullptr;
            while (true == is_odd_check || true == is_even_check)
            {
                if (true == is_even_check && 0 == length % 2)   // even length check
                {
                    left = pivot - length/2 + 1;
                    right = pivot + length/2;
                    std::cout <<  "(even)length=" << length << ", pivot=" << *pivot <<", left=" << *left << ", right=" << *right << std::endl;
                    if (*left != *right)
                    {
                        std::cout << "is_even_check = false" << std::endl;
                        is_even_check = false;
                    }
                    else
                    {
                        if (length > max_palindrome_len)
                        { 
                            found = left; max_palindrome_len = length;
                            std::cout << "max_palindrome_len = " << length << ", found=" << left << std::endl;
                        }
                    }
                }
                else if (true == is_odd_check && 1 == length % 2)// odd length check
                {
                    left = pivot - length/2;
                    right = pivot + length/2;
                    std::cout <<  "(odd)length=" << length << ", pivot=" << *pivot <<", left=" << *left << ", right=" << *right << std::endl;
                    if (*left != *right)
                    {
                        std::cout << "is_odd_check = false" << std::endl;
                        is_odd_check = false;
                    }
                    else
                    {
                        if (length > max_palindrome_len)
                        { 
                            found = left; max_palindrome_len = length;
                            std::cout << "max_palindrome_len = " << length << ", found=" << left << std::endl;
                        }
                    }
                }

                if (begin == left || '\0' == right+1)
                {
                    break;
                }
                ++length;
            }

            return found;
        }
    };

    void TestPalin()
    {
        Solution solver;
        auto found = solver.longestPalindrome("123abba");
        std::cout << "PALINDROME = " << found << std::endl;
    }