Question:
Write a function that finds the longest palindromic substring in a string.
ex: findLongstPal('affaptbbcracecarf') returns 'racecar'
Answer:
string findLongstHelp(string str, int& maxi, int& maxj){
int len = str.length();
bool flag[] = new int[len+1];
int max=0;
for (int i = 0;i<len+1;++i){
flag[i] = i;
}
for(int i=len;i>=0;--i){
for(int j=i;j>=0;--j){
if(isPalindrome(str, j, i)){
int diff = i-j+1;
if(diff >= i-flag[i]){
flag[i] = j;
}
}
}
if(i-flag[i] > max){
maxi = i;
maxj = flag[i];
}
}
return str.substring(maxj,maxi-maxj+1);
}
bool isPalindrome(string str, int m, int n){
while(m<n){
if(str[m] != str[n]) break;
m++;
n--;
}
if(m<n) return false;
return true;
}
No comments:
Post a Comment