Finding the longest palindrome from the given string

Question

Recently I came across this problem which instructs me to find the longest substring which is a palindrome:

As we all know, a palindrome is a word that equals its reverse. Here are some examples of palindromes: malayalam, gag, appa, amma.

We consider any sequence consisting of the letters of the English alphabet to be a word. So axxb,abbba and bbbccddx are words for our purpose. And aaabbaaa, abbba and bbb are examples of palindromes.

By a subword of a word, we mean a contiguous subsequence of the word. For example the subwords of the word abbba are a, b, ab, bb, ba, abb, bbb, bba, abbb, bbba and abbba.

In this task you will given a word and you must find the longest subword of this word that is also a palindrome.

For example if the given word is abbba then the answer is abbba. If the given word is abcbcabbacba then the answer is bcabbacb.

I got this with dynamic programming, but for larger test cases it seems I am breaking the memory barrier. When the length is about 4500, it gives me a segmentation fault. That's probably because 4500 x 4500 = 20250000, which is about \$2*10^7\$, and the size of my boolean array is too much in front of the imposed memory limit of 64 MB.

#include <iostream>
#include <cstring>
#include <string>

void longestpalin(std::string str,int n){
    bool table[n][n];                   //boolean table for keeping records of palindromes 
    std::memset(table,0,sizeof(table));

    int maxLength = 0;
    for(int i=0;i<n;i++){
        table[i][i] = true; // obviously every letter is palindrome of itself
    }

    int start = 0;

    for(int i=0;i<n-1;i++){
        if(str[i] == str[i+1]){
            table[i][i+1] = true; //two letters repeated is also a palindrome
            maxLength = 2;
            start = i;
        }
    }

    for(int k=3;k <= n;k++){
        for(int i=0;i<n-k+1;i++){
            int j = i + k - 1;
            if(table[i+1][j-1]&&str[i] == str[j]){//checking whether the middle letters are in a pallindrome or not
                table[i][j] = true; 
                if(k > maxLength){
                    maxLength = k;
                    start = i;
                }
            }
        }
    }
    std::cout << maxLength << std::endl;
    std::cout << str.substr(start,maxLength) << std::endl;
}

int main (int argc, char const* argv[])
{
    int n;
    std::cin >> n;
    std::string word;
    std::cin >> word;
    longestpalin(word,n);
    return 0;
} 

Is there a better approach to avoid a segmentation fault?

Answer 1

bool table[n][n];                   //boolean table for keeping records of palindromes 

Variable-length arrays are not part of the C++ standard, and in any case they are a bad idea. (Some C++ compilers support it anyway as a non-standard feature.) Stacks aren't meant to handle such large frames. If you need a large variable-length array, use a std::vector or a std::bitset instead.

Answer 2

You will hit a 64MB memory restriction regardless of how you allocate an array 20+ million entries strong. So you need to revisit an algorithm.

The problem doesn't look like a DP to begin with. Notice that the mere initialization of the array drives the time complexity to be quadratic. If you are happy with the quadratic time, notice that a naive approach requires constant space.

And since the quadratic time complexity will TLE on any decent OJ, you shall check out Manacher's algorithm.