Numero minimo di caratteri da inserire al termine di una stringa per renderlo un palindromo

Question

La domanda è come questo--

Dobbiamo trovare il numero minimo di caratteri da inserire alla fine del una stringa per renderlo un palindromo.

Quindi, nei miei sforzi per risolvere questo problema, ho calcolato che questo è equivalente alla ricerca della più grande sottostringa palindromica che è anche un suffisso della stringa.

Potrei farlo facilmente in O (n^2) ma sto cercando una soluzione O (n) che è probabilmente possibile utilizzando KMP modificato. Qualcuno, per favore, aiutami a capire.

Answer 1

Ho un approccio che utilizza l'hashing pubblicato come risposta here.

In effetti, è possibile utilizzare anche KMP. È possibile calcolare il prefix function per la stringa invertita, e quindi scorrere la stringa iniziale da sinistra a destra:

KMP calcola una funzione prefix[i] = longest prefix of the string that is a suffix of string[1..i]

Tuttavia, vogliamo sapere the longest suffix of our string that is a prefix of the reversed string. Perché? Se abbiamo:

15232 => reverse = 23251 

Poi il suffisso più lungo della stringa che è un prefisso della stringa invertita è 232. Questo è un palindromo e ci permette di trovare quello che stai chiedendo perché un suffisso della stringa si sovrappone a un prefisso della stringa invertita se i due sono palindromi.

avete la casi:

prefix[i] = length - i => you can get a palindrome of 
      length 2*prefix[i] centered at i and i+1 

prefix[i] = length - i + 1 => you can get a palindrome of 
      length 2*prefix[i] - 1 centered at i 

prefix[i] < length - i => you can't have a palindrome, ignore this position 

Quindi è sufficiente per calcolare la funzione di prefisso dell'algoritmo KMP.

Answer 2

Un semplice codice per inserire il numero minimo di caratteri e tornare loro di fare la stringa dato un pallindrome

#include <bits/stdc++.h> 
using namespace std; 
bool isPalin(char *s,int x,int l) 
{ 
    for(int i=x,j=l-1;i<j;i++,j--) 
     if(s[i]!=s[j]) 
      return 0; 
    return 1; 
} 
char * f(char *s) 
{ 
    // if s is NULL return NULL 
    if(!s) 
     return NULL; 
    int i,l,j; 
    l=strlen(s); 
    for(i=0;i<l;i++) 
    { 
     // check if string is pallindrome from [i...l-1] 
     if(isPalin(s,i,l) == 1) 
      break; 
    } 
    // if s is already a pallindrome return NULL 
    if(i==0) 
     return NULL; 
    int k=0; 
    // make a char* 
    char *ans = new char[i+1]; 
    for(i-=1;i>=0;i--) 
     ans[k++]=s[i]; 
    ans[k++]='\0'; 
    return ans; 
} 

int main() { 
    char *a = "wxytabbat"; 
    cout<<f(a)<<"\n"; 
    return 0; 
}