Программа палиндрома и условный переход или перемещение зависят от неинициализированных значений - PullRequest
Новая
       21

Программа палиндрома и условный переход или перемещение зависят от неинициализированных значений

1 голос
/ 16 июня 2019

Подобные вопросы были заданы.Эта проблема является общим нахождением самой длинной подстроки палиндрома.

Возникли некоторые проблемы с чтением дампа ошибок, я думаю, что у меня есть индекс массива из-за связанной ошибки, но я не могу отследить его, используя мои журналы, выходные операторы и проверку моей проверки состояния.Добавлены комментарии для обозначения номеров строк.Запуск этого в подсистеме Linux для Windows.

Вывод 

> valgrind --track-origins=yes ./a.out
==665== Memcheck, a memory error detector
==665== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==665== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==665== Command: ./a.out
==665==
==665== error calling PR_SET_PTRACER, vgdb might block
==665== Conditional jump or move depends on uninitialised value(s)
==665==    at 0x401C00: Solution::longestPalindrome(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (main.cpp:61)
==665==    by 0x400F05: main (main.cpp:79)
==665==  Uninitialised value was created by a stack allocation
==665==    at 0x401752: Solution::longestPalindrome(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (main.cpp:28)
==665==
aaaabbaa HAS: aabbaa <-

Код 

class Solution
{
    public:
        std::pair<int,int> expandFrom(const std::string s, int left_char, int right_char, const int str_len)
        {
            while(left_char >= 0 && right_char <= str_len && s[left_char] == s[right_char]) {
                --left_char;
                ++right_char;
            }

            return {left_char+1, right_char-1};
        }

        const std::string longestPalindrome(const std::string s) // line 28
        {
            if(s.length() == 0 || s.length() >= 1000) { return ""; }
            else if(s.length() == 1) { return s; }

            const int str_length = s.length();
            std::string longest_palindrome = "";

            std::pair<int, int> range1 = {0,0};
            std::pair<int, int> range2 = {0,0};
            int length1 = 0;
            int length2 = 0;

            for(int mid = 0; mid < str_length; ++mid) {
                range1 = expandFrom(s, mid, mid, str_length);
                range2 = expandFrom(s, mid, mid+1, str_length);
                length1 = range1.second - range1.first;
                length2 = range2.second - range2.first;
                if (length1 > length2) {
                    if (length1 > longest_palindrome.length()) {
                        longest_palindrome = s.substr(range1.first, range1.second);
                        if(longest_palindrome[range1.first] != longest_palindrome[range1.second]) {
                            longest_palindrome = s.substr(range1.first, range1.second + 1);
                        }
                    }
                } else {
                    if (length2 > longest_palindrome.length()) { // line 61
                        longest_palindrome = s.substr(range2.first, range2.second);
                        if(longest_palindrome[range2.first] != longest_palindrome[range2.second]) {
                            longest_palindrome = s.substr(range2.first, range2.second + 1);
                        }
                    }
                }
            }

            return longest_palindrome;
        }
};

int main()
{
    Solution s;
    std::cout << "aaaabbaa HAS: " << s.longestPalindrome("aaaabbaa") << " <-\n\n"; // line 79    
}

1 Ответ

0 голосов
/ 16 июня 2019

Логика вашего кода явно неверна ...

Ваш код выполняет оператор: 

longest_palindrome = s.substr(range2.first, range2.second);

поэтому longest_palindrome теперь представляет собой строку длиной range2.second - range2.first, и допустимые индексы идут от 0 до range2.second - range2.first - 1.

Однако в следующем выражении вы обращаетесь к нему, используя range2.first и range2.second в качестве индексов.

...