Palíndromo fragmentado más largo posible

Dada una string, la tarea es devolver la longitud de su palíndromo fragmentado más largo posible. Se entiende por palíndromo formado por substring en el caso de que no esté formado por caracteres de la string. Para una mejor comprensión mira el ejemplo 

Ejemplos:

Input : ghiabcdefhelloadamhelloabcdefghi 
Output : 7
(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)

Input : merchant
Output : 1
(merchant)

Input : antaprezatepzapreanta
Output : 11
(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)

Input : geeksforgeeks
Output : 3
(geeks)(for)(geeks)

La idea completa es crear fragmentos de izquierda a derecha y recursivamente. 

Como puede ver, podemos hacer coincidir la substring del fragmento del lado izquierdo y hacerlo coincidir con el fragmento exacto del lado derecho. Una vez que obtenemos una coincidencia, recursivamente contamos la longitud del palíndromo fragmentado más largo posible en la string restante. Terminamos la recursión una vez que no queda ninguna string o cuando no se pueden encontrar más partes fragmentadas válidas. 

Implementación:

// C++ program to find the length of longest palindromic chunk
#include <bits/stdc++.h>
using namespace std;
 
// Here curr_str is the string whose LCP is needed
// len is length of string evaluated till now
// and str is original string
int LPCRec(string curr_str, int count, int len, string str)
    {
        // if there is noting at all!!
        if (curr_str.size()==0)
            return (0);
 
        // if a single letter is left out
        if (curr_str.size() <= 1)
        {
            if (count != 0 && (str.size() - len )<= 1)
                return (count + 1);
            else
                return (1);
        }
 
        // for each length of substring chunk in string
        int n = curr_str.size();
        for (int i = 0; i < n/2; i++)
        {
            // if left side chunk and right side chunk
            // are same
            if (curr_str.substr(0, i+1) == curr_str.substr(n-1-i,i+1))
            {
                // Call LCP for the part between the
                // chunks and add 2 to the result.
                // Length of string evaluated till
                // now is increased by (i+1)*2
                return LPCRec(curr_str.substr(i+1, n-2-2*i), //
                        count + 2,
                        len + (i+1)*2, str);
            }
        }
 
        return count + 1;
    }
 
 
// Wrapper over LPCRec()
int LPC(string str)
{
    return LPCRec(str, 0, 0, str);
}
 
 
// driver function
int main()
{
    cout<<"V : "<<LPC("V")<<endl;
    cout<<"VOLVO : " << LPC("VOLVO")<<endl;
    cout<<"VOLVOV : " << LPC("VOLVOV")<<endl;
    cout<<"ghiabcdefhelloadamhelloabcdefghi : "<<
        LPC("ghiabcdefhelloadamhelloabcdefghi")<<endl;
         
    cout<<"ghiabcdefhelloadamhelloabcdefghik : "<<
                    LPC("ghiabcdefhelloadamhelloabcdefghik")<<endl;
 
    cout<<"antaprezatepzapreanta : " <<
                    LPC("antaprezatepzapreanta");
}
 
// This code is contributed by Pushpesh Raj

/* Java program to find the length of longest palindromic
   chunk */
import java.util.*;
import java.lang.*;
import java.io.*;
 
class LongestPalindromicChunk
{
    // Here s is the string whose LCP is needed
    // ln is length of string evaluated till now
    // and str is original string
    private static int LPCRec(String curr_str, int count,
                             int len, String str)
    {
        // if there is noting at all!!
        if (curr_str == null || curr_str.isEmpty())
            return (0);
 
        // if a single letter is left out
        if (curr_str.length() <= 1)
        {
            if (count != 0 && str.length() - len <= 1)
                return (count + 1);
            else
                return (1);
        }
 
        // for each length of substring chunk in string
        int n = curr_str.length();
        for (int i = 0; i < n/2; i++)
        {
            // if left side chunk and right side chunk
            // are same
            if (curr_str.substring(0, i + 1).
                equals(curr_str.substring(n-1-i, n)))
            {
                // Call LCP for the part between the
                // chunks and add 2 to the result.
                // Length of string evaluated till
                // now is increased by (i+1)*2
                return LPCRec(curr_str.substring(i+1, n-1-i),
                           count + 2,
                           len + (i+1)*2, str);
            }
        }
 
        return count + 1;
    }
 
    // Wrapper over LPCRec()
    public static int LPC(String str)
    {
        return LPCRec(str, 0, 0, str);
    }
 
    // driver function
    public static void main(String[] args)
    {
        System.out.println("V : " + LPC("V"));
        System.out.println("VOLVO : " + LPC("VOLVO"));
        System.out.println("VOLVOV : " + LPC("VOLVOV"));
        System.out.println("ghiabcdefhelloadamhelloabcdefghi : " +
                        LPC("ghiabcdefhelloadamhelloabcdefghi"));
 
        System.out.println("ghiabcdefhelloadamhelloabcdefghik : " +
                        LPC("ghiabcdefhelloadamhelloabcdefghik"));
 
        System.out.println("antaprezatepzapreanta : " +
                        LPC("antaprezatepzapreanta"));
    }
}

# Python3 program to find length of
# longest palindromic chunk
 
# Here curr_str is the string whose
# LCP is needed leng is length of
# string evaluated till now and s 
# is original string
def LPCRec(curr_str, count, leng, s):
     
    # If there is nothing at all!!
    if not curr_str:
        return 0
 
    # If a single letter is left out
    if len(curr_str) <= 1:
        if count != 0 and len(s) - leng <= 1:
            return (count + 1)
        else:
            return 1
 
    # For each length of substring
    # chunk in string
    n = len(curr_str)
    for i in range(n // 2):
         
        # If left side chunk and right
        # side chunk are same
        if (curr_str[0 : i + 1] ==
            curr_str[n - 1 - i : n]):
             
            # Call LCP for the part between the
            # chunks and add 2 to the result.
            # Length of string evaluated till
            # now is increased by (i+1)*2
            return LPCRec(curr_str[i + 1 : n - 1 - i],
                          count + 2, leng + (i + 1) * 2, s)
                           
    return count + 1
 
# Wrapper over LPCRec()
def LPC(s):
     
    return LPCRec(s, 0, 0, s)
 
# Driver code
print("V :", LPC("V"))
print("VOLVO :", LPC("VOLVO"))
print("VOLVOV :", LPC("VOLVOV"))
print("ghiabcdefhelloadamhelloabcdefghi :",
  LPC("ghiabcdefhelloadamhelloabcdefghi"))
 
print("ghiabcdefhelloadamhelloabcdefghik :",
  LPC("ghiabcdefhelloadamhelloabcdefghik"))
 
print("antaprezatepzapreanta :",
  LPC("antaprezatepzapreanta"))
 
# This code is contributed by Prateek Gupta

// C# program to find length of
// longest palindromic chunk
using System;
 
class GFG
{
// Here s is the string whose LCP
// is needed ln is length of string
// evaluated till now and str is
// original string
private static int LPCRec(string curr_str, int count,
                          int len, string str)
{
    // if there is noting at all!!
    if (string.ReferenceEquals(curr_str, null) ||
                               curr_str.Length == 0)
    {
        return (0);
    }
 
    // if a single letter is left out
    if (curr_str.Length <= 1)
    {
        if (count != 0 && str.Length - len <= 1)
        {
            return (count + 1);
        }
        else
        {
            return (1);
        }
    }
 
    // for each length of substring
    // chunk in string
    int n = curr_str.Length;
    for (int i = 0; i < n / 2; i++)
    {
        // if left side chunk and right side chunk
        // are same
        if (curr_str.Substring(0, i + 1).Equals(
            curr_str.Substring(n - 1 - i, n - (n - 1 - i))))
        {
            // Call LCP for the part between the
            // chunks and add 2 to the result.
            // Length of string evaluated till
            // now is increased by (i+1)*2
            return LPCRec(curr_str.Substring(i + 1, (n - 1 - i) -
                         (i + 1)), count + 2, len + (i + 1) * 2, str);
        }
    }
 
    return count + 1;
}
 
// Wrapper over LPCRec()
public static int LPC(string str)
{
    return LPCRec(str, 0, 0, str);
}
 
// Driver Code
public static void Main(string[] args)
{
    Console.WriteLine("V : " + LPC("V"));
    Console.WriteLine("VOLVO : " + LPC("VOLVO"));
    Console.WriteLine("VOLVOV : " + LPC("VOLVOV"));
    Console.WriteLine("ghiabcdefhelloadamhelloabcdefghi : " +
                    LPC("ghiabcdefhelloadamhelloabcdefghi"));
 
    Console.WriteLine("ghiabcdefhelloadamhelloabcdefghik : " +
                    LPC("ghiabcdefhelloadamhelloabcdefghik"));
 
    Console.WriteLine("antaprezatepzapreanta : " +
                    LPC("antaprezatepzapreanta"));
}
}
 
// This code is contributed by Shrikant13

<script>
 
// JavaScript program to find length of
// longest palindromic chunk
 
// Here curr_str is the string whose
// LCP is needed leng is length of
// string evaluated till now and s 
// is original string
function LPCRec(curr_str, count, leng, s){
     
    // If there is nothing at all!!
    if(!curr_str)
        return 0
 
    // If a single letter is left out
    if(curr_str.length <= 1){
        if (count != 0 && s.length - leng <= 1)
            return (count + 1)
        else
            return 1
    }
 
    // For each length of substring
    // chunk in string
    let n = curr_str.length
    for(let i=0;i<Math.floor(n/2);i++){
         
        // If left side chunk and right
        // side chunk are same
        if (curr_str.substring(0,i+1) == curr_str.substring(n-1-i,n))
             
            // Call LCP for the part between the
            // chunks and add 2 to the result.
            // Length of string evaluated till
            // now is increased by (i+1)*2
            return LPCRec(curr_str.substring(i + 1,n - 1 - i), count + 2, leng + (i + 1) * 2, s)
    }
                           
    return count + 1
}
 
// Wrapper over LPCRec()
function LPC(s){
     
    return LPCRec(s, 0, 0, s)
}
 
// Driver code
document.write("V :", LPC("V"),"</br>")
document.write("VOLVO :", LPC("VOLVO"),"</br>")
document.write("VOLVOV :", LPC("VOLVOV"),"</br>")
document.write("ghiabcdefhelloadamhelloabcdefghi :",
  LPC("ghiabcdefhelloadamhelloabcdefghi"),"</br>")
 
document.write("ghiabcdefhelloadamhelloabcdefghik :",
  LPC("ghiabcdefhelloadamhelloabcdefghik"),"</br>")
 
document.write("antaprezatepzapreanta :",
  LPC("antaprezatepzapreanta"),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

V : 1
VOLVO : 3
VOLVOV : 5
ghiabcdefhelloadamhelloabcdefghi : 7
ghiabcdefhelloadamhelloabcdefghik : 1
antaprezatepzapreanta : 11

A continuación se muestra la implementación de C++ con memorización para el problema anterior. 

Implementación:

#include <climits>
#include <iostream>
#include <unordered_map>
using namespace std;
 
unordered_map<string, int> mem;
 
int process(string& s, int l, int r)
{
    int ans = 1;
    if (l > r)
        return 0;
    // check if we've already solved this
    if (mem.find(s.substr(l, r - l + 1)) != mem.end())
        return mem[s.substr(l, r - l + 1)];
    for (int len = 1; len <= (r - l + 1) / 2; len++) {
        if (s.substr(l, len) == s.substr(r - len + 1, len))
            ans = max(ans,
                      2 + process(s, l + len, r - len));
    }
    // remember result for future
    mem[s.substr(l, r - l + 1)] = ans;
    return ans;
}
 
int LPC(string s) { return process(s, 0, s.length() - 1); }
 
int main()
{
    cout << LPC("aaaaabaababbaabaaababababababababbbbaaaaa")
         << endl;
    return 0;
}

# Python code for the approach
 
mem = {}
 
def process(s,l,r):
    global mem
    ans = 1
    if (l > r):
        return 0
    # check if we've already solved this
    if (s[l: r+1] in mem):
        return mem[s[l: r+1]]
    for Len in range(1,(r-l+1)//2 + 1,1):
        if (s[l: Len+l] == s[r-Len+1:r+1]):
            ans = max(ans, 2 + process(s, l+Len, r-Len))
    # remember result for future
    mem[s[l: r+1]] = ans
    return ans
 
def LPC(s):
    return process(s, 0, len(s)-1)
 
# driver code
 
print(LPC("aaaaabaababbaabaaababababababababbbbaaaaa"))
 
# This code is contributed by shinjanpatra.

13

Este artículo es una contribución de Aditya Nihal Kumar Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.