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?