Skip to content

Instantly share code, notes, and snippets.

@stevekrenzel
Created June 25, 2011 10:05
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/1046332 to your computer and use it in GitHub Desktop.
Save stevekrenzel/1046332 to your computer and use it in GitHub Desktop.
Longest palindrome in C++ (fast version)
#include <iostream>
#include <string>
using namespace std;
string findLongestPalindrome(string str) {
int max_lower = 0, max_upper = 0, len = str.length(), lower = 0, upper = 0;
for(int i = 0; i < len; i++) {
upper = i + 1, lower = i;
for(int j = 0; j < 2; j++) {
lower = i - j;
for(;lower >= 0 and upper < len and str[lower] == str[upper]
;upper++, lower--);
if((max_upper - max_lower) < (upper - lower - 2)) {
max_lower = lower + 1, max_upper = upper - 1;
}
}
}
return str.substr(max_lower, max_upper - max_lower + 1);
}
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