时间戳

首页 > 解决方案 > 回文程序和条件跳转或移动取决于未初始化的值

c++ - 回文程序和条件跳转或移动取决于未初始化的值

问题描述

有人问过类似的问题。这个问题是寻找最长回文子串的常见问题。

在读取错误转储时遇到一些问题，我认为我有一个数组索引超出范围错误，但无法使用我的日志、输出语句和查看我的条件检查来跟踪它。添加了注释以表示行号。在 Windows 的 Linux 子系统上运行它。

输出

> 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    
}

标签： c++arrayslinuxvalgrind

解决方案

你的代码逻辑显然是错误的......

您的代码执行以下语句：

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

所以longest_palindrome现在是一串长度range2.second - range2.first和有效索引从0到range2.second - range2.first - 1包含。

然而，在下一条语句中，您使用range2.first和range2.second作为索引来访问它。

推荐阅读