Tuesday, September 3, 2013

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

string getpalin(int i, int j, string s)
{
 string result = "";
 while(i >= 0 && j <= s.size())
 {
  if(s[i] != s[j])
   break;
  i--;
  j++;
 }

 i++;
 j--;
 if(i <= j)
 {
  result = s.substr(i, j - i +1);
 }

 return result;
}

string longestPalindrome(string s) {
 if(s.size() <= 1)
  return s;
 string result = "";
 for(int i  =0; i < s.size(); i++)
 {
  string t  = getpalin(i, i, s);
  if(t.size() > result.size())
   result = t;
 }

 for(int i  =0; i < s.size() -1; i++)
 {
  string t  = getpalin(i, i+1, s);
  if(t.size() > result.size())
   result = t;
 }

 return result;
}

No comments:

Post a Comment