Skip to content

Instantly share code, notes, and snippets.

@stevekrenzel
Created June 23, 2011 09:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save stevekrenzel/1042187 to your computer and use it in GitHub Desktop.
Save stevekrenzel/1042187 to your computer and use it in GitHub Desktop.
Longest palindrome in C++ (readable version)
#include <iostream>
#include <string>
using namespace std;
#define MAX_STR(a, b) (((a.length()) > (b.length())) ? (a) : (b))
string getPalindromeAt(string str, int lower, int upper) {
for(;lower >= 0 and upper < str.length() and str[lower] == str[upper]
;upper++, lower--);
return str.substr(lower + 1, upper - lower - 1);
}
string getPalindromeAt(int center, string str) {
string even = getPalindromeAt(str, center, center + 1);
string odd = getPalindromeAt(str, center - 1, center + 1);
return MAX_STR(even, odd);
}
string findLongestPalindrome(string str) {
string max = "";
for(int i = 0; i < str.length(); i++) {
max = MAX_STR(max, getPalindromeAt(i, str));
}
return max;
}
int main(void) {
cout << findLongestPalindrome("ISAAS") << " = SASS"<< endl;
cout << findLongestPalindrome("a") << " = a" << endl;
cout << findLongestPalindrome("ab") << " = a" << endl;
cout << findLongestPalindrome("bba") << " = bb" << endl;
cout << findLongestPalindrome("abb") << " = bb" <<endl;
cout << findLongestPalindrome("aba") << " = aba" << endl;
cout << findLongestPalindrome("Very fast racecar.") << " = racecar" << endl;
cout << findLongestPalindrome("a bb aba abba abcba cddc cdc dd c") << " = ba abba ab" << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment