Finding the Longest Palindrome

The other day I was doing a programming challenge that required me to find the longest palindrome within a string. The challenge was to do it in at least O(N)2 complexity.  I found this to be fairly interesting. The challenge read like so:

Given a string S, find the longest substring in S that is the same in reverse and print it to the standard output.

So for example, if I had the string given was:  s= “abcdxyzyxabcdaaa” . Then the longest palindrome within it is “xyzyx “. We need to write a function to find this for us.  The nature of the challenge just needed me to write a function for a web back-end, so the example code below does not have main, or a defined string, etc. Also, there are O(N) solutions for this problem if you seek them, but they are a little more complicated.

#include <iostream>
#include <string>

using namespace std;

void longest_palind(const string &s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
bool table[100][100] = {false};

for (int i = 0; i < n; i++)
{
table[i][i] = true;
}
for (int i = 0; i < n-1; i++)
{
if (s[i] == s[i+1]) {
table[i][i+1] = true;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s[i] == s[j] && table[i+1][j-1]) {
table[i][j] = true;
longestBegin = i;
maxLen = len;
}
}
}
cout << s.substr(longestBegin, maxLen);
}
Advertisements