Palíndromo más largo de una string formado por la concatenación de su prefijo y sufijo

Dada una string str que consta de letras inglesas minúsculas, la tarea es encontrar la string palindrómica T más larga que satisfaga la siguiente condición: 
 

• T = p + m + s donde p y s son el prefijo y el sufijo de la string str respectivamente y la string m es el prefijo o el sufijo de la string str después de eliminar tanto p como s de ella.
• La string formada por la concatenación de p y s es un palíndromo en sí mismo.
• Cualquiera de las strings p y s puede ser una string vacía.

Ejemplos: 
 

Entrada: str = “abcdfdcecba” 
Salida: abcdfdcba 
Explicación: 
Aquí, p = “abc” 
s = “cba” 
m = “dfd” 
p + s = “abccba” que es un palíndromo y m = “dfd” es el prefijo después eliminando el prefijo y el sufijo de la string str. Por lo tanto, T = “abcdfdcba”.
Entrada: str = “geeksforgeeks” 
Salida: g 
Explicación: 
Aquí, p = “” 
s = “g” 
m = “” 
p + s = “”, que es un palíndromo y m = “g” es el prefijo después de eliminar el prefijo y el sufijo de la string str. Por lo tanto, T = “g”. 
 

Enfoque: La idea para este problema es dividir la respuesta en tres partes, de modo que habrá una parte de sufijo y prefijo de la string dada que formará un palíndromo que formará el principio y el final de la string de respuesta. Ahora, después de eliminar estos prefijos y sufijos de la string dada, podemos encontrar el sufijo o string de prefijos de longitud máxima (que podemos llamar midPalindrome) que es palindrómico.
Por lo tanto, la string de respuesta estará dada por: 
 

answer = prefix + midPalindrome + suffix

Se pueden seguir los siguientes pasos para calcular la respuesta al problema: 
 

• Encuentre la longitud hasta la cual el sufijo y el prefijo de str forman juntos un palíndromo.
• Elimine las substrings de sufijo y prefijo que ya forman un palíndromo de str y guárdelas en strings separadas.
• Verifique todas las substrings de prefijo y sufijo en la string str restante y encuentre la más larga de dichas strings.
• Finalmente, combina las tres partes de la respuesta y devuélvela.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the longest
// palindrome in a string formed by
// concatenating its prefix and suffix
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether
// the string is a palindrome
bool isPalindrome(string r)
{
    string p = r;
 
    // Reverse the string to
    // compare with the
    // original string
    reverse(p.begin(), p.end());
 
    // Check if both are same
    return (r == p);
}
 
// Function to find the longest
// palindrome in a string formed by
// concatenating its prefix and suffix
string PrefixSuffixPalindrome(string str)
{
    // Length of the string
    int n = str.size(), len = 0;
 
    // Finding the length upto which
    // the suffix and prefix forms a
    // palindrome together
    for (int i = 0; i < n / 2; i++) {
        if (str[i] != str[n - i - 1]) {
            len = i;
            break;
        }
    }
 
    // Check whether the string
    // has prefix and suffix substrings
    // which are palindromes.
    string prefix = "", suffix = "";
    string midPal = "";
 
    // Removing the suffix and prefix
    // substrings which already forms
    // a palindrome and storing them
    // in separate strings
    prefix = str.substr(0, len);
    suffix = str.substr(n - len);
    str = str.substr(len, n - 2 * len);
 
    // Check all prefix substrings
    // in the remaining string str
    for (int i = 1; i <= str.size(); i++) {
        string y = str.substr(0, i);
 
        // Check if the prefix substring
        // is a palindrome
        if (isPalindrome(y)) {
 
            // If the prefix substring
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.size() < y.size()) {
                midPal = y;
            }
        }
    }
 
    // Check all the suffix substrings
    // in the remaining string str
    for (int i = 1; i <= str.size(); i++) {
        string y = str.substr(str.size() - i);
 
        // Check if the suffix substring
        // is a palindrome
        if (isPalindrome(y)) {
 
            // If the suffix substring
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.size() < y.size()) {
                midPal = y;
            }
        }
    }
 
    // Combining all the three parts
    // of the answer
    string answer = prefix + midPal + suffix;
 
    return answer;
}
 
// Driver code
int main()
{
    string str = "abcdfdcecba";
 
    cout << PrefixSuffixPalindrome(str) << "\n";
 
    return 0;
}

// Java program to find the longest
// palindrome in a String formed by
// concatenating its prefix and suffix
import java.util.*;
 
class GFG{
  
// Function to check whether
// the String is a palindrome
static boolean isPalindrome(String r)
{
    String p = r;
  
    // Reverse the String to
    // compare with the
    // original String
    p = reverse(p);
  
    // Check if both are same
    return (r.equals(p));
}
  
// Function to find the longest
// palindrome in a String formed by
// concatenating its prefix and suffix
static String PrefixSuffixPalindrome(String str)
{
    // Length of the String
    int n = str.length(), len = 0;
  
    // Finding the length upto which
    // the suffix and prefix forms a
    // palindrome together
    for (int i = 0; i < n / 2; i++) {
        if (str.charAt(i) != str.charAt(n - i - 1)) {
            len = i;
            break;
        }
    }
  
    // Check whether the String
    // has prefix and suffix subStrings
    // which are palindromes.
    String prefix = "", suffix = "";
    String midPal = "";
  
    // Removing the suffix and prefix
    // subStrings which already forms
    // a palindrome and storing them
    // in separate Strings
    prefix = str.substring(0, len);
    suffix = str.substring(n - len);
    str = str.substring(len, (n - 2 * len) + len);
  
    // Check all prefix subStrings
    // in the remaining String str
    for (int i = 1; i <= str.length(); i++) {
        String y = str.substring(0, i);
  
        // Check if the prefix subString
        // is a palindrome
        if (isPalindrome(y)) {
  
            // If the prefix subString
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.length() < y.length()) {
                midPal = y;
            }
        }
    }
  
    // Check all the suffix subStrings
    // in the remaining String str
    for (int i = 1; i <= str.length(); i++) {
        String y = str.substring(str.length() - i);
  
        // Check if the suffix subString
        // is a palindrome
        if (isPalindrome(y)) {
  
            // If the suffix subString
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.length() < y.length()) {
                midPal = y;
            }
        }
    }
  
    // Combining all the parts
    // of the answer
    String answer = prefix + midPal + suffix;
  
    return answer;
}
static String reverse(String input) {
    char[] a = input.toCharArray();
    int l, r = a.length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.valueOf(a);
}
  
// Driver code
public static void main(String[] args)
{
    String str = "abcdfdcecba";
  
    System.out.print(PrefixSuffixPalindrome(str));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the longest
# palindrome in a string formed by
# concatenating its prefix and suffix
  
# Function to check whether
# the string is a palindrome
def isPalindrome(r):
 
    p = r
  
    # Reverse the string to
    # compare with the
    # original string
    p = "".join(reversed(p))
  
    # Check if both are same
    return (r == p)
  
# Function to find the longest
# palindrome in a string formed by
# concatenating its prefix and suffix
def PrefixSuffixPalindrome(st):
 
    # Length of the string
    n = len(st)
    length = 0
  
    # Finding the length upto which
    # the suffix and prefix forms a
    # palindrome together
    for i in range( n // 2):
        if (st[i] != st[n - i - 1]):
            length = i
            break
  
    # Check whether the string
    # has prefix and suffix substrings
    # which are palindromes.
    prefix = ""
    suffix = ""
    midPal = ""
  
    # Removing the suffix and prefix
    # substrings which already forms
    # a palindrome and storing them
    # in separate strings
    prefix = st[:length]
    suffix = st[n - length:]
    st = st[length: n - 2 * length+length]
 
    # Check all prefix substrings
    # in the remaining string str
    for i in range(1,len(st)+1):
        y = st[0: i]
  
        # Check if the prefix substring
        # is a palindrome
        if (isPalindrome(y)):
  
            # If the prefix substring
            # is a palindrome then check
            # if it is of maximum length
            # so far
            if (len(midPal) < len(y)):
                midPal = y
  
    # Check all the suffix substrings
    # in the remaining string str
    for i in range(1,len(st)+1):
        y = st[len(st)-i]
  
        # Check if the suffix substring
        # is a palindrome
        if (isPalindrome(y)):
  
            # If the suffix substring
            # is a palindrome then check
            # if it is of maximum length
            # so far
            if (len(midPal) < len(y)):
                midPal = y
  
    # Combining all the parts
    # of the answer
    answer = prefix + midPal + suffix
  
    return answer
  
# Driver code
if __name__ == "__main__":
     
    st = "abcdfdcecba";
  
    print(PrefixSuffixPalindrome(st))
  
# This code is contributed by chitranayal
    

// C# program to find the longest
// palindrome in a String formed by
// concatenating its prefix and suffix
using System;
 
class GFG{
   
// Function to check whether
// the String is a palindrome
static bool isPalindrome(String r)
{
    String p = r;
   
    // Reverse the String to
    // compare with the
    // original String
    p = reverse(p);
   
    // Check if both are same
    return (r.Equals(p));
}
   
// Function to find the longest
// palindrome in a String formed by
// concatenating its prefix and suffix
static String PrefixSuffixPalindrome(String str)
{
    // Length of the String
    int n = str.Length, len = 0;
   
    // Finding the length upto which
    // the suffix and prefix forms a
    // palindrome together
    for (int i = 0; i < n / 2; i++) {
        if (str[i] != str[n - i - 1]) {
            len = i;
            break;
        }
    }
   
    // Check whether the String
    // has prefix and suffix subStrings
    // which are palindromes.
    String prefix = "", suffix = "";
    String midPal = "";
   
    // Removing the suffix and prefix
    // subStrings which already forms
    // a palindrome and storing them
    // in separate Strings
    prefix = str.Substring(0, len);
    suffix = str.Substring(n - len);
    str = str.Substring(len, (n - 2 * len) + len);
   
    // Check all prefix subStrings
    // in the remaining String str
    for (int i = 1; i <= str.Length; i++) {
        String y = str.Substring(0, i);
   
        // Check if the prefix subString
        // is a palindrome
        if (isPalindrome(y)) {
   
            // If the prefix subString
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.Length < y.Length) {
                midPal = y;
            }
        }
    }
   
    // Check all the suffix subStrings
    // in the remaining String str
    for (int i = 1; i <= str.Length; i++) {
        String y = str.Substring(str.Length - i);
   
        // Check if the suffix subString
        // is a palindrome
        if (isPalindrome(y)) {
   
            // If the suffix subString
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.Length < y.Length) {
                midPal = y;
            }
        }
    }
   
    // Combining all the parts
    // of the answer
    String answer = prefix + midPal + suffix;
   
    return answer;
}
static String reverse(String input) {
    char[] a = input.ToCharArray();
    int l, r = a.Length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.Join("",a);
}
   
// Driver code
public static void Main(String[] args)
{
    String str = "abcdfdcecba";
   
    Console.Write(PrefixSuffixPalindrome(str));
}
}
  
// This code is contributed by 29AjayKumar

<script>
// Javascript program to find the longest
// palindrome in a String formed by
// concatenating its prefix and suffix
 
// Function to check whether
// the String is a palindrome
function isPalindrome(r)
{
    let p = r;
    
    // Reverse the String to
    // compare with the
    // original String
    p = reverse(p);
    
    // Check if both are same
    return (r == (p));
}
 
// Function to find the longest
// palindrome in a String formed by
// concatenating its prefix and suffix
function PrefixSuffixPalindrome(str)
{
    // Length of the String
    let n = str.length, len = 0;
    
    // Finding the length upto which
    // the suffix and prefix forms a
    // palindrome together
    for (let i = 0; i < n / 2; i++) {
        if (str[i] != str[n - i - 1]) {
            len = i;
            break;
        }
    }
    
    // Check whether the String
    // has prefix and suffix subStrings
    // which are palindromes.
    let prefix = "", suffix = "";
    let midPal = "";
    
    // Removing the suffix and prefix
    // subStrings which already forms
    // a palindrome and storing them
    // in separate Strings
    prefix = str.substring(0, len);
    suffix = str.substring(n - len);
    str = str.substring(len, (n - 2 * len) + len);
    
    // Check all prefix subStrings
    // in the remaining String str
    for (let i = 1; i <= str.length; i++) {
        let y = str.substring(0, i);
    
        // Check if the prefix subString
        // is a palindrome
        if (isPalindrome(y)) {
    
            // If the prefix subString
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.length < y.length) {
                midPal = y;
            }
        }
    }
    
    // Check all the suffix subStrings
    // in the remaining String str
    for (let i = 1; i <= str.length; i++) {
        let y = str.substring(str.length - i);
    
        // Check if the suffix subString
        // is a palindrome
        if (isPalindrome(y)) {
    
            // If the suffix subString
            // is a palindrome then check
            // if it is of maximum length
            // so far
            if (midPal.length < y.length) {
                midPal = y;
            }
        }
    }
    
    // Combining all the parts
    // of the answer
    let answer = prefix + midPal + suffix;
    
    return answer;
}
 
function reverse(input)
{
    let a = input.split("");
    let l, r = a.length - 1;
    for (l = 0; l < r; l++, r--) {
        let temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return (a).join("");
}
 
// Driver code
let str = "abcdfdcecba";
document.write(PrefixSuffixPalindrome(str));
 
// This code is contributed by avanitrachhadiya2155
</script>

abcdfdcba