La string palindrómica más larga posible después de la eliminación de una substring

Dada una string str , la tarea es encontrar la string palindrómica más larga que se puede obtener de ella después de eliminar una substring.

Ejemplos: 

Entrada: str = “abcdefghiedcba” 
Salida: “abcdeiedcba” 
Explicación: La eliminación de la substring “fgh” deja la string restante palindrómica

Entrada: str = “abba” 
Salida: “abba” 
Explicación: Eliminación de la substring “” ya que la string dada ya es palindrómica. 

Acercarse: 

• Encuentre el par más largo posible de substrings A y B de ambos extremos de la string dada que están invertidas entre sí.
• Quítelos de la string original.
• Encuentre las substrings palindrómicas más largas de ambos extremos de la string restante usando KMP y considere la substring que es más larga.
• Agregue las strings A y B al principio y al final de esta substring palindrómica respectivamente para obtener el resultado deseado.

El siguiente código es la implementación del enfoque anterior:

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

// Java Implementation of the
// above approach
import java.util.*;
 
class GFG{
     
// Function to find the longest palindrome
// from the start of the String using KMP match
static String findPalindrome(String C)
{
    String S = C;
    S = reverse(S);
     
    // Append S(reverse of C) to C
    C = C + "&" + S;
    int n = C.length();
    int []longestPalindrome = new int[n];
    longestPalindrome[0] = 0;
    int len = 0;
    int i = 1;
     
    // Use KMP algorithm
    while (i < n) {
        if (C.charAt(i) == C.charAt(len)) {
            len++;
            longestPalindrome[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = longestPalindrome[len - 1];
            }
            else {
                longestPalindrome[i] = 0;
                i++;
            }
        }
    }
    String ans = C.substring(0, longestPalindrome[n - 1]);
    return ans;
}
 
// Function to return longest palindromic
// String possible from the given String
// after removal of any subString
static String findAns(String s)
{
    // Initialize three Strings A, B AND F
    String A = "";
    String B = "";
    String F = "";
 
    int i = 0;
    int j = s.length() - 1;
    int len = s.length();
     
    // Loop to find longest subStrings
    // from both ends which are
    // reverse of each other
    while (i < j && s.charAt(i) == s.charAt(j)) {
        i = i + 1;
        j = j - 1;
    }
     
    if (i > 0)
    {
        A = s.substring(0, i);
        B = s.substring(len - i, len);
    }
 
    // Proceed to third step of our approach
    if (len > 2 * i)
    {
        // Remove the subStrings A and B
        String C = s.substring(i, (s.length() - 2 * i) + i);
         
        // Find the longest palindromic
        // subString from beginning of C
        String D = findPalindrome(C);
         
        // Find the longest palindromic
        // subString from end of C
        C = reverse(C);
        String E = findPalindrome(C);
         
        // Store the maximum of D and E in F
        if (D.length() > E.length()) {
            F = D;
        }
        else {
            F = E;
        }
    }
     
    // Find the final answer
    String answer = A + F + B;
     
    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 = "abcdefghiedcba";
    System.out.print(findAns(str) +"\n");
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the
# above approach
 
# Function to find the longest
# palindrome from the start of
# the string using KMP match
def findPalindrome(C):
     
    S = C[::-1]
     
    # Append S(reverse of C)  to C
    C = C[:] + '&' + S
     
    n = len(C)
    longestPalindrome = [0 for i in range(n)]
    longestPalindrome[0] = 0
     
    ll = 0
    i = 1
     
    # Use KMP algorithm
    while (i < n):
        if (C[i] == C[ll]):
            ll += 1
            longestPalindrome[i] = ll
            i += 1
         
        else:
             
            if (ll != 0):
                ll = longestPalindrome[ll - 1]
            else:
                longestPalindrome[i] = 0
                i += 1
             
    ans = C[0:longestPalindrome[n - 1]]
     
    return ans
 
# Function to return longest palindromic
# string possible from the given string
# after removal of any substring
def findAns(s):
 
    # Initialize three strings
    # A, B AND F
    A = ""
    B = ""
    F = ""
   
    i = 0
    j = len(s) - 1
    ll = len(s)
       
    # Loop to find longest substrings
    # from both ends which are 
    # reverse of each other
    while (i < j and s[i] == s[j]):
        i = i + 1
        j = j - 1
     
    if (i > 0):
        A = s[0 : i]
        B = s[ll - i : ll]
      
    # Proceed to third step of our approach
    if (ll > 2 * i): 
     
        # Remove the substrings A and B
        C = s[i : i + (len(s) - 2 * i)]
         
        # Find the longest palindromic
        # substring from beginning of C
        D = findPalindrome(C)
           
        # Find the longest palindromic
        # substring from end of C
        C = C[::-1]
         
        E = findPalindrome(C)
           
        # Store the maximum of D and E in F
        if (len(D) > len(E)):
            F = D
        else:
            F = E
     
    # Find the final answer
    answer = A + F + B
       
    return answer
 
# Driver code
if __name__=="__main__":
     
    str = "abcdefghiedcba"
     
    print(findAns(str))
 
# This code is contributed by rutvik_56

// C# Implementation of the
// above approach
using System;
 
class GFG{
      
// Function to find the longest palindrome
// from the start of the String using KMP match
static String findPalindrome(String C)
{
    String S = C;
    S = reverse(S);
      
    // Append S(reverse of C) to C
    C = C + "&" + S;
    int n = C.Length;
    int []longestPalindrome = new int[n];
    longestPalindrome[0] = 0;
    int len = 0;
    int i = 1;
      
    // Use KMP algorithm
    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.Substring(0, longestPalindrome[n - 1]);
    return ans;
}
  
// Function to return longest palindromic
// String possible from the given String
// after removal of any subString
static String findAns(String s)
{
    // Initialize three Strings A, B AND F
    String A = "";
    String B = "";
    String F = "";
  
    int i = 0;
    int j = s.Length - 1;
    int len = s.Length;
      
    // Loop to find longest subStrings
    // from both ends which are
    // reverse of each other
    while (i < j && s[i] == s[j]) {
        i = i + 1;
        j = j - 1;
    }
      
    if (i > 0)
    {
        A = s.Substring(0, i);
        B = s.Substring(len - i, i);
    }
  
    // Proceed to third step of our approach
    if (len > 2 * i)
    {
        // Remove the subStrings A and B
        String C = s.Substring(i, (s.Length - 2 * i));
          
        // Find the longest palindromic
        // subString from beginning of C
        String D = findPalindrome(C);
          
        // Find the longest palindromic
        // subString from end of C
        C = reverse(C);
        String E = findPalindrome(C);
          
        // Store the maximum of D and E in F
        if (D.Length > E.Length) {
            F = D;
        }
        else {
            F = E;
        }
    }
      
    // Find the readonly answer
    String answer = A + F + B;
      
    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 = "abcdefghiedcba";
    Console.Write(findAns(str) +"\n");
}
}
 
// This code is contributed by Rajput-Ji

<script>
      // JavaScript Implementation of the
      // above approach
      // Function to find the longest palindrome
      // from the start of the String using KMP match
      function findPalindrome(C) {
        var S = C;
        S = reverse(S);
 
        // Append S(reverse of C) to C
        C = C + "&" + S;
        var n = C.length;
        var longestPalindrome = new Array(n).fill(0);
        longestPalindrome[0] = 0;
        var len = 0;
        var i = 1;
 
        // Use KMP algorithm
        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++;
            }
          }
        }
        var ans = C.substring(0, longestPalindrome[n - 1]);
        return ans;
      }
 
      // Function to return longest palindromic
      // String possible from the given String
      // after removal of any subString
      function findAns(s) {
        // Initialize three Strings A, B AND F
        var A = "";
        var B = "";
        var F = "";
 
        var i = 0;
        var j = s.length - 1;
        var len = s.length;
 
        // Loop to find longest subStrings
        // from both ends which are
        // reverse of each other
        while (i < j && s[i] === s[j]) {
          i = i + 1;
          j = j - 1;
        }
 
        if (i > 0) {
          A = s.substring(0, i);
          B = s.substring(len - i, len);
        }
 
        // Proceed to third step of our approach
        if (len > 2 * i) {
          // Remove the subStrings A and B
          var C = s.substring(i, i + (s.length - 2 * i));
 
          // Find the longest palindromic
          // subString from beginning of C
          var D = findPalindrome(C);
 
          // Find the longest palindromic
          // subString from end of C
          C = reverse(C);
          var E = findPalindrome(C);
 
          // Store the maximum of D and E in F
          if (D.length > E.length) {
            F = D;
          } else {
            F = E;
          }
        }
 
        // Find the readonly answer
        var answer = A + F + B;
 
        return answer;
      }
 
      function reverse(input) {
        var a = input.split("");
        var r = a.length - 1;
        for (var l = 0; l < r; l++, r--) {
          var temp = a[l];
          a[l] = a[r];
          a[r] = temp;
        }
        return a.join("");
      }
 
      // Driver Code
      var str = "abcdefghiedcba";
      document.write(findAns(str));
       
      // This code is contributed by rdtank.
    </script>

abcdeiedcba

Complejidad temporal: O(N)
Espacio auxiliar : O(N)