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