Imprime el prefijo palindrómico más largo de una string dada

Dada una string str , la tarea es encontrar el prefijo palindrómico más largo de la string dada.

Ejemplos: 

Entrada: str = “abaac” 
Salida: aba 
Explicación: 
El prefijo más largo de la string dada que es palindrómico es “aba”.

Entrada: str = “abacabaxyz” 
Salida: abacaba 
Explicación: 
Los prefijos de la string dada que es palindrómica son “aba” y “abacabaxyz”. 
Pero el más largo de los dos es “abacabaxyz”. 
 

Enfoque ingenuo: la idea es generar toda la substring de la string dada a partir del índice inicial y verificar si las substrings son palindrómicas o no. La cuerda palindrómica con una longitud máxima es la cuerda resultante.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest prefix
// which is palindromic
void LongestPalindromicPrefix(string s)
{
 
    // Find the length of the given string
    int n = s.length();
 
    // For storing the length of longest
    // prefix palindrome
    int max_len = 0;
 
    // Loop to check the substring of all
    // length from 1 to N which is palindrome
    for (int len = 1; len <= n; len++) {
 
        // String of length i
        string temp = s.substr(0, len);
 
        // To store the reversed of temp
        string temp2 = temp;
 
        // Reversing string temp2
        reverse(temp2.begin(), temp2.end());
 
        // If string temp is palindromic
        // then update the length
        if (temp == temp2) {
            max_len = len;
        }
    }
 
    // Print the palindromic string of
    // max_len
    cout << s.substr(0, max_len);
}
 
// Driver Code
int main()
{
 
    // Given string
    string str = "abaab";
 
    // Function Call
    LongestPalindromicPrefix(str);
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the longest prefix
// which is palindromic
static void LongestPalindromicPrefix(String s)
{
 
    // Find the length of the given String
    int n = s.length();
 
    // For storing the length of longest
    // prefix palindrome
    int max_len = 0;
 
    // Loop to check the subString of all
    // length from 1 to N which is palindrome
    for (int len = 1; len <= n; len++)
    {
 
        // String of length i
        String temp = s.substring(0, len);
 
        // To store the reversed of temp
        String temp2 = temp;
 
        // Reversing String temp2
        temp2 = reverse(temp2);
 
        // If String temp is palindromic
        // then update the length
        if (temp.equals(temp2))
        {
            max_len = len;
        }
    }
 
    // Print the palindromic String of
    // max_len
    System.out.print(s.substring(0, max_len));
}
 
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)
{
 
    // Given String
    String str = "abaab";
 
    // Function Call
    LongestPalindromicPrefix(str);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to find the longest prefix
# which is palindrome
def LongestPalindromicPrefix(string):
     
    # Find the length of the given string
    n = len(string)
     
    # For storing the length of longest
    # Prefix Palindrome
    max_len = 0
     
    # Loop to check the substring of all
    # length from 1 to n which is palindrome
    for length in range(0, n + 1):
         
        # String of length i
        temp = string[0:length]
         
        # To store the value of temp
        temp2 = temp
         
        # Reversing the value of temp
        temp3 = temp2[::-1]
         
        # If string temp is palindromic
        # then update the length
        if temp == temp3:
            max_len = length
     
    # Print the palindromic string
    # of max_len
    print(string[0:max_len])
 
# Driver code
if __name__ == '__main__' :
     
    string = "abaac";
     
    # Function call
    LongestPalindromicPrefix(string)
     
# This code is contributed by virusbuddah_

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the longest prefix
// which is palindromic
static void longestPalindromicPrefix(String s)
{
 
    // Find the length of the given String
    int n = s.Length;
 
    // For storing the length of longest
    // prefix palindrome
    int max_len = 0;
 
    // Loop to check the subString of all
    // length from 1 to N which is palindrome
    for (int len = 1; len <= n; len++)
    {
 
        // String of length i
        String temp = s.Substring(0, len);
 
        // To store the reversed of temp
        String temp2 = temp;
 
        // Reversing String temp2
        temp2 = reverse(temp2);
 
        // If String temp is palindromic
        // then update the length
        if (temp.Equals(temp2))
        {
            max_len = len;
        }
    }
 
    // Print the palindromic String of
    // max_len
    Console.Write(s.Substring(0, max_len));
}
 
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)
{
 
    // Given String
    String str = "abaab";
 
    // Function Call
    longestPalindromicPrefix(str);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
    // JavaScript program for the above approach
     
    // Function to find the longest prefix
    // which is palindromic
    function LongestPalindromicPrefix(s)
    {
 
        // Find the length of the given String
        let n = s.length;
 
        // For storing the length of longest
        // prefix palindrome
        let max_len = 0;
 
        // Loop to check the subString of all
        // length from 1 to N which is palindrome
        for (let len = 1; len <= n; len++)
        {
 
            // String of length i
            let temp = s.substring(0, len);
 
            // To store the reversed of temp
            let temp2 = temp;
 
            // Reversing String temp2
            temp2 = reverse(temp2);
 
            // If String temp is palindromic
            // then update the length
            if (temp == temp2)
            {
                max_len = len;
            }
        }
 
        // Print the palindromic String of
        // max_len
        document.write(s.substring(0, max_len));
    }
 
    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("");
    }
     
    // Given String
    let str = "abaab";
  
    // Function Call
    LongestPalindromicPrefix(str);
 
</script>

aba

Complejidad de tiempo: O(N ² ) , donde N es la longitud de la string dada.

Enfoque eficiente: la idea es utilizar el algoritmo de preprocesamiento Algoritmo KMP . A continuación se muestran los pasos: 

• Cree una string temporal (digamos str2 ) que es:

str2 = str + '?' reverse(str);

• Cree una array (digamos lps[] ) del tamaño de la longitud de la string str2 que almacenará el prefijo palindrómico más largo que también es un sufijo de la string str2 .
• Actualice el lps[] utilizando el algoritmo de preprocesamiento del algoritmo de búsqueda KMP .
• lps[longitud(str2) – 1 ] dará la longitud de la string de prefijo palindrómico más larga de la string dada str .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest prefix
// which is palindromic
void LongestPalindromicPrefix(string str)
{
 
    // Create temporary string
    string temp = str + '?';
 
    // Reverse the string str
    reverse(str.begin(), str.end());
 
    // Append string str to temp
    temp += str;
 
    // Find the length of string temp
    int n = temp.length();
 
    // lps[] array for string temp
    int lps[n];
 
    // Initialise every value with zero
    fill(lps, lps + n, 0);
 
    // Iterate the string temp
    for (int i = 1; i < n; i++) {
 
        // Length of longest prefix
        // till less than i
        int len = lps[i - 1];
 
        // Calculate length for i+1
        while (len > 0
               && temp[len] != temp[i]) {
            len = lps[len - 1];
        }
 
        // If character at current index
        // len are same then increment
        // length by 1
        if (temp[i] == temp[len]) {
            len++;
        }
 
        // Update the length at current
        // index to len
        lps[i] = len;
    }
 
    // Print the palindromic string of
    // max_len
    cout << temp.substr(0, lps[n - 1]);
}
 
// Driver's Code
int main()
{
 
    // Given string
    string str = "abaab";
 
    // Function Call
    LongestPalindromicPrefix(str);
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the longest
// prefix which is palindromic
static void LongestPalindromicPrefix(String str)
{
 
    // Create temporary String
    String temp = str + '?';
 
    // Reverse the String str
    str = reverse(str);
 
    // Append String str to temp
    temp += str;
 
    // Find the length of String temp
    int n = temp.length();
 
    // lps[] array for String temp
    int []lps = new int[n];
 
    // Initialise every value with zero
    Arrays.fill(lps, 0);
 
    // Iterate the String temp
    for(int i = 1; i < n; i++)
    {
         
       // Length of longest prefix
       // till less than i
       int len = lps[i - 1];
        
       // Calculate length for i+1
       while (len > 0 && temp.charAt(len) !=
                         temp.charAt(i))
       {
           len = lps[len - 1];
       }
        
       // If character at current index
       // len are same then increment
       // length by 1
       if (temp.charAt(i) == temp.charAt(len))
       {
           len++;
       }
        
       // Update the length at current
       // index to len
       lps[i] = len;
    }
 
    // Print the palindromic String
    // of max_len
    System.out.print(temp.substring(0, lps[n - 1]));
}
 
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)
{
 
    // Given String
    String str = "abaab";
 
    // Function Call
    LongestPalindromicPrefix(str);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to find the longest prefix
# which is palindromic
def LongestPalindromicPrefix(Str):
 
    # Create temporary string
    temp = Str + "?"
 
    # Reverse the string Str
    Str = Str[::-1]
 
    # Append string Str to temp
    temp = temp + Str
 
    # Find the length of string temp
    n = len(temp)
 
    # lps[] array for string temp
    lps = [0] * n
 
    # Iterate the string temp
    for i in range(1, n):
 
        # Length of longest prefix
        # till less than i
        Len = lps[i - 1]
 
        # Calculate length for i+1
        while (Len > 0 and temp[Len] != temp[i]):
            Len = lps[Len - 1]
 
        # If character at current index
        # Len are same then increment
        # length by 1
        if (temp[i] == temp[Len]):
            Len += 1
 
        # Update the length at current
        # index to Len
        lps[i] = Len
 
    # Print the palindromic string
    # of max_len
    print(temp[0 : lps[n - 1]])
 
# Driver Code
if __name__ == '__main__':
     
    # Given string
    Str = "abaab"
 
    # Function call
    LongestPalindromicPrefix(Str)
 
# This code is contributed by himanshu77

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the longest
// prefix which is palindromic
static void longestPalindromicPrefix(String str)
{
     
    // Create temporary String
    String temp = str + '?';
 
    // Reverse the String str
    str = reverse(str);
 
    // Append String str to temp
    temp += str;
 
    // Find the length of String temp
    int n = temp.Length;
 
    // lps[] array for String temp
    int []lps = new int[n];
 
    // Iterate the String temp
    for(int i = 1; i < n; i++)
    {
        
       // Length of longest prefix
       // till less than i
       int len = lps[i - 1];
        
       // Calculate length for i+1
       while (len > 0 && temp[len] != temp[i])
       {
           len = lps[len - 1];
       }
        
       // If character at current index
       // len are same then increment
       // length by 1
       if (temp[i] == temp[len])
       {
           len++;
       }
        
       // Update the length at current
       // index to len
       lps[i] = len;
    }
     
    // Print the palindromic String
    // of max_len
    Console.Write(temp.Substring(0, lps[n - 1]));
}
 
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)
{
 
    // Given String
    String str = "abaab";
 
    // Function Call
    longestPalindromicPrefix(str);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program for the above approach
 
// Function to find the longest
// prefix which is palindromic
function longestPalindromicPrefix(str)
{
     
    // Create temporary String
    let temp = str + '?';
 
    // Reverse the String str
    str = reverse(str);
 
    // Append String str to temp
    temp += str;
 
    // Find the length of String temp
    let n = temp.length;
 
    // lps[] array for String temp
    let lps = new Array(n);
    lps.fill(0);
 
    // Iterate the String temp
    for(let i = 1; i < n; i++)
    {
         
        // Length of longest prefix
        // till less than i
        let len = lps[i - 1];
         
        // Calculate length for i+1
        while (len > 0 && temp[len] != temp[i])
        {
            len = lps[len - 1];
        }
         
        // If character at current index
        // len are same then increment
        // length by 1
        if (temp[i] == temp[len])
        {
            len++;
        }
         
        // Update the length at current
        // index to len
        lps[i] = len;
    }
 
    // Print the palindromic String
    // of max_len
    document.write(temp.substring(0, lps[n - 1]));
}
 
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
 
// Given String
let str = "abaab";
 
// Function Call
longestPalindromicPrefix(str);
 
// This code is contributed by mukesh07
 
</script>

aba

Complejidad de tiempo: O(N) , donde N es la longitud de la string dada. 
Espacio auxiliar: O(N) , donde N es la longitud de la string dada.