longest palindromic substring. Error: AddressSanitizer, heap overflow

Question

#include<string>
#include<cstring>

class Solution {
    void shift_left(char* c, const short unsigned int bits) {
        const unsigned short int size = sizeof(c);
        memmove(c, c+bits, size - bits);
        memset(c+size-bits, 0, bits);
    }
public:
    string longestPalindrome(string s) {
        char* output = new char[s.length()];
        output[0] = s[0];
        string res = "";
        
        char* n = output;
        auto e = s.begin() + 1;
        while(e != s.end()) {
            char letter = *e;
            char* c = n;
            (*++n) = letter;
            if((letter != *c) && (c == &output[0] || letter != (*--c)) ) {
                ++e;
                continue;
            }
            while((++e) != s.end() && c != &output[0]) {
                if((letter = *e) != (*--c)) {
                    const unsigned short int bits = c - output + 1;
                    shift_left(output, bits);
                    n -= bits;
                    break;
                }
                (*++n) = letter;
            }
            string temp(output);
            res = temp.length() > res.length()? temp : res;
            shift_left(output, 1);
            --n;
        }
        return res;
    }
};

input string longestPalindrome("babad");

the program works fine and prints out "bab" as the longest palindrome but there's a heap overflow somewhere. Error like this appears: Read of size 6 at ...memory address... thread T0 "babad" is size 5 and after going over this for an hour. I don't see the point where the iteration ever exceeds 5 There is 3 pointers here that iterate. e as the element of string s. n which is the pointer to the next char of output. and c which is a copy of n and decrements until it reaches the address of &output[0]. maybe it's something with the memmove or memset since I've never used it before. I'm completely lost

`char* c = n;` looks very suspicious. However please don't use leetcode to learn yourself C++. Your code is already showing its bad influence (hardly readable, falling back on memset/memmove). Trying to optimize before it works etc... So get a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or have a go at https://www.learncpp.com/. To learn C++, then come back later to leetcode to train your problem solving skills (or just to have fun). — Pepijn Kramer, Nov 29 '22 at 05:10
Several erros: Most important: sizeof(c) will not calculate the length of the given array. It will always return the same value (presumably 8). It will return the length of the pointer variable "c". Additionally, you do `new` but never `delete`. If you remove all C-Style arrays and new and pointers for owned memory, then everything will be fine. — A M, Nov 29 '22 at 06:12

Arseny Staroverov · Answer 1 · 2022-11-29T10:24:50.067

TL;DR : mixture of char* and std::string are not really good idea if you don't understand how exactly it works.

If you want to length of string you cant do this const unsigned short int size = sizeof(c); (sizeof will return size of pointer (which is commonly 4 on 32-bit machine and 8 on 64-bit machine). You must do this instead: const size_t size = strlen(c);

Address sanitizers is right that you (indirectly) are trying to get an memory which not belongs to you.

How does constructor of string from char* works?

Answer: char* is considered as c-style string, which means that it must be null '\0' terminated.

More details: constructor of string from char* calls strlen-like function which looks like about this:

https://en.cppreference.com/w/cpp/string/byte/strlen

int strlen(char *begin){
    int k = 0;
    while (*begin != '\0'){
        ++k;
        ++begin;
    }
    return k;
}

If c-style char* string does not contain '\0' it cause accessing memory which doesn't belongs to you.

How to fix?

Answer (two options):

not use mixture of char* and std::string
char* output = new char[s.length()]; replace with char* output = new char[s.length() + 1]; memset(output, 0, s.length() + 1);

Also you must delete all memory which you newed. So add delete[] output; before return res;

longest palindromic substring. Error: AddressSanitizer, heap overflow

1 Answers1