Número mínimo de apéndices necesarios para hacer un palíndromo de cuerdas

Dada una string s, necesitamos indicar los caracteres mínimos que se agregarán (inserción al final) para hacer un palíndromo de string. 

Ejemplos: 

Input : s = "abede"
Output : 2
We can make string palindrome as "abedeba"
by adding ba at the end of the string.

Input : s = "aabb"
Output : 2
We can make string palindrome as"aabbaa"
by adding aa at the end of the string.

La solución se puede lograr eliminando caracteres del comienzo de la string uno por uno y verificando si la string es palíndromo o no. 
Por ejemplo, considere la string anterior, s = “abede” . 
Comprobamos si la cuerda es palíndromo o no. 
El resultado es falso, luego eliminamos el carácter del comienzo de una string y ahora la string se convierte en «bede» .
Comprobamos si la cuerda es palíndromo o no. El resultado es nuevamente falso, luego eliminamos el carácter del comienzo de una string y ahora la string se convierte en “ede” .
Comprobamos si la cuerda es palíndromo o no. El resultado es verdadero, por lo que la salida se convierte en 2, que es el número de caracteres eliminados de la string. 

Implementación:

// C program to find minimum number of appends
// needed to make a string Palindrome
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
 
// Checking if the string is palindrome or not
bool isPalindrome(char *str)
{
    int len = strlen(str);
 
    // single character is always palindrome
    if (len == 1)
        return true;
 
    // pointing to first character
    char *ptr1 = str;
 
    // pointing to last character
    char *ptr2 = str+len-1;
 
    while (ptr2 > ptr1)
    {
        if (*ptr1 != *ptr2)
            return false;
        ptr1++;
        ptr2--;
    }
 
    return true;
}
 
// Recursive function to count number of appends
int noOfAppends(char s[])
{
    if (isPalindrome(s))
        return 0;
 
    // Removing first character of string by
    // incrementing base address pointer.
    s++;
 
    return 1 + noOfAppends(s);
}
 
// Driver program to test above functions
int main()
{
    char s[] = "abede";
    printf("%d\n", noOfAppends(s));
    return 0;
}

// Java program to find minimum number of appends
// needed to make a string Palindrome
class GFG
{
 
// Checking if the string is palindrome or not
static boolean isPalindrome(char []str)
{
    int len = str.length;
   
    // single character is always palindrome
    if (len == 1)
        return true;
   
    // pointing to first character
    int ptr1 = 0;
     
    // pointing to last character
    int  ptr2 = len-1;
   
    while (ptr2 >= ptr1)
    {
        if (str[ptr1] != str[ptr2])
            return false;
        ptr1++;
        ptr2--;
    }
   
    return true;
}
 
// Recursive function to count number of appends
static int noOfAppends(String s)
{
    if (isPalindrome(s.toCharArray()))
        return 0;
 
    // Removing first character of string by
    // incrementing base address pointer.
    s=s.substring(1);
 
    return 1 + noOfAppends(s);
}
 
// Driver code
public static void main(String arr[])
{
    String s = "abede";
    System.out.printf("%d\n", noOfAppends(s));
}
}
 
// This code contributed by Rajput-Ji

# Python3 program to find minimum number of appends
# needed to make a String Palindrome
 
# Checking if the String is palindrome or not
def isPalindrome(Str):
 
    Len = len(Str)
 
    # single character is always palindrome
    if (Len == 1):
        return True
 
    # pointing to first character
    ptr1 = 0
 
    # pointing to last character
    ptr2 = Len - 1
 
    while (ptr2 > ptr1):
 
        if (Str[ptr1] != Str[ptr2]):
            return False
        ptr1 += 1
        ptr2 -= 1
 
    return True
 
# Recursive function to count number of appends
def noOfAppends(s):
 
    if (isPalindrome(s)):
        return 0
 
    # Removing first character of String by
    # incrementing base address pointer.
    del s[0]
 
    return 1 + noOfAppends(s)
 
# Driver Code
se = "abede"
s = [i for i in se]
print(noOfAppends(s))
 
# This code is contributed by Mohit Kumar

// C# program to find minimum number of appends
// needed to make a string Palindrome
using System;
 
class GFG
{
 
// Checking if the string is palindrome or not
static Boolean isPalindrome(char []str)
{
    int len = str.Length;
 
    // single character is always palindrome
    if (len == 1)
        return true;
 
    // pointing to first character
    char ptr1 = str[0];
 
    // pointing to last character
    char ptr2 = str[len-1];
 
    while (ptr2 > ptr1)
    {
        if (ptr1 != ptr2)
            return false;
        ptr1++;
        ptr2--;
    }
 
    return true;
}
 
// Recursive function to count number of appends
static int noOfAppends(String s)
{
    if (isPalindrome(s.ToCharArray()))
        return 0;
 
    // Removing first character of string by
    // incrementing base address pointer.
    s=s.Substring(1);
 
    return 1 + noOfAppends(s);
}
 
// Driver code
public static void Main(String []arr)
{
    String s = "abede";
    Console.Write("{0}\n", noOfAppends(s));
}
}
 
// This code has been contributed by 29AjayKumar

<script>
// Javascript program to find minimum number of appends
// needed to make a string Palindrome
     
    // Checking if the string is palindrome or not
    function isPalindrome(str)
    {
        let len = str.length;
    
    // single character is always palindrome
    if (len == 1)
        return true;
    
    // pointing to first character
    let ptr1 = 0;
      
    // pointing to last character
    let  ptr2 = len-1;
    
    while (ptr2 >= ptr1)
    {
        if (str[ptr1] != str[ptr2])
            return false;
        ptr1++;
        ptr2--;
    }
    
    return true;
    }
     
    // Recursive function to count number of appends
    function noOfAppends(s)
    {
        if (isPalindrome(s.split("")))
            return 0;
  
    // Removing first character of string by
    // incrementing base address pointer.
    s=s.substring(1);
  
    return 1 + noOfAppends(s);
    }
     
    // Driver code
    let s = "abede";
    document.write(noOfAppends(s));
     
// This code is contributed by unknown2108
</script>

2

Complejidad de Tiempo: O(n ² )
Espacio Auxiliar: O(n)

Enfoque eficiente:

También tenemos un algoritmo que toma la ayuda del algoritmo Knuth Morris Pratt , que es O(n) Time Complexity.

La idea básica detrás del enfoque es que calculamos la substring más grande desde el final y la longitud de la string menos este valor es el número mínimo de anexos. La lógica es intuitiva, no necesitamos anexar el palíndromo y sólo los que no forman el palíndromo. Para encontrar este palíndromo más grande desde el final, invertimos la string, calculamos el DFA e invertimos la string nuevamente (recuperando así la string original) y encontramos el estado final, que representa el número de coincidencias de la string con la string reverenciada y por lo tanto, obtenemos la substring más grande que es un palíndromo desde el final, en tiempo O(n).

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

// CPP program for above approach
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
 
// This class builds the dfa and
// precomputes the state.
// See KMP algorithm for explanation
class kmp_numeric {
private:
    int n;
    int** dfa;
 
public:
    kmp_numeric(string& s)
    {
        n = s.length();
        int c = 256;
 
        // Create dfa
        dfa = new int*[n];
 
        // Iterate from 0 to n
        for (int i = 0; i < n; i++)
            dfa[i] = new int;
 
        int x = 0;
 
        // Iterate from 0 to n
        for (int i = 0; i < c; i++)
            dfa[0][i] = 0;
 
        // Initialise dfa[0][s[0]] = 1
        dfa[0][s[0]] = 1;
 
        // Iterate i from 1 to n-1
        for (int i = 1; i < n; i++) {
 
            // Iterate j from 0 to c - 1
            for (int j = 0; j < c; j++) {
                dfa[i][j] = dfa[x][j];
            }
 
            dfa[i][s[i]] = i + 1;
            x = dfa[x][s[i]];
        }
    }
 
    // This function finds the overlap
    // between two strings,by
    // changing the state.
    int longest_overlap(string& query)
    {
 
        // q1 is length of query
        int ql = query.length();
        int state = 0;
 
        // Iterate from 0 to q1 - 1
        for (int i = 0; i < ql; i++) {
            state = dfa[state][query[i]];
        }
        return state;
    }
};
 
int min_appends(string& s)
{
 
    // Reverse the string.
    reverse(s.begin(), s.end());
 
    // Build the DFA for the
    // reversed String
    kmp_numeric kmp = s;
 
    // Get the original string back
    reverse(s.begin(), s.end());
 
    // Largest overlap in this case is the
    // largest string from the end which
    // is a palindrome.
    int ans = s.length() - kmp.longest_overlap(s);
    return ans;
}
 
// Driver Code
int main()
{
    string s = "deep";
    // Answer : 3
 
    string t = "sososososos";
    // Answer : 0
 
    cout << min_appends(s) << endl;
    cout << min_appends(t) << endl;
}

3
0

Sugerencia de:   Pratik Priyadarsan 

Complejidad de Tiempo: O(n ² )
Espacio Auxiliar: O(n ² )

 Artículo relacionado: 
Programación dinámica | Juego 28 (Inserciones mínimas para formar un palíndromo)

Este artículo es una contribución de Aarti_Rathi y Shubham Chaudhary . 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.