Longest palindromic string possible after removal of a substring | C ++ Implementation of the above approach ; Function to find the longest palindrome from the start of the string using KMP match ; Append S ( reverse of C ) to C ; Use KMP algorithm ; Function to return longest palindromic string possible from the given string after removal of any substring ; Initialize three strings A , B AND F ; Loop to find longest substrings from both ends which are reverse of each other ; Proceed to third step of our approach ; Remove the substrings A and B ; Find the longest palindromic substring from beginning of C ; Find the longest palindromic substring from end of C ; Store the maximum of D and E in F ; Find the final answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string findPalindrome ( string C ) { string S = C ; reverse ( S . begin ( ) , S . end ( ) ) ; C = C + " & " + S ; int n = C . length ( ) ; int longestPalindrome [ n ] ; longestPalindrome [ 0 ] = 0 ; int len = 0 ; int i = 1 ; while ( i < n ) { if ( C [ i ] == C [ len ] ) { len ++ ; longestPalindrome [ i ] = len ; i ++ ; } else { if ( len != 0 ) { len = longestPalindrome [ len - 1 ] ; } else { longestPalindrome [ i ] = 0 ; i ++ ; } } } string ans = C . substr ( 0 , longestPalindrome [ n - 1 ] ) ; return ans ; } string findAns ( string s ) { string A = " " ; string B = " " ; string F = " " ; int i = 0 ; int j = s . length ( ) - 1 ; int len = s . length ( ) ; while ( i < j && s [ i ] == s [ j ] ) { i = i + 1 ; j = j - 1 ; } if ( i > 0 ) { A = s . substr ( 0 , i ) ; B = s . substr ( len - i , i ) ; } if ( len > 2 * i ) { string C = s . substr ( i , s . length ( ) - 2 * i ) ; string D = findPalindrome ( C ) ; reverse ( C . begin ( ) , C . end ( ) ) ; string E = findPalindrome ( C ) ; if ( D . length ( ) > E . length ( ) ) { F = D ; } else { F = E ; } } string answer = A + F + B ; return answer ; } int main ( ) { string str = " abcdefghiedcba " ; cout << findAns ( str ) << endl ; }