fueanta

Longest Palindromic Substring

Jun 13th, 2017
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. class Solution {
  7. public:
  8.     string longestPalindrome(string s) {
  9.         int length = 0, initial = 0;
  10.         for (int i = 0; i < s.size(); ++i)
  11.         {
  12.             int len1 = getPalindromeLength(s, i, i);
  13.             int len2 = getPalindromeLength(s, i, i + 1);
  14.             int len = (len1 > len2) ? len1 : len2;
  15.            
  16.             if (len > length)
  17.             {
  18.                 length = len;
  19.                 initial = i - (length - 1) / 2;
  20.             }
  21.         }
  22.         return s.substr(initial, length);
  23.     }
  24.     int getPalindromeLength(string s, int low, int high)
  25.     {
  26.         while (low >= 0 && high < s.size() && s[low] == s[high])
  27.         {
  28.             --low; ++high;
  29.         }
  30.         return (high - low) - 1;
  31.     }
  32. };
  33.  
  34. int main(void)
  35. {
  36.     Solution s;
  37.     cout << s.longestPalindrome("babad") << endl;
  38.     return 0;
  39. }
RAW Paste Data