Palindrome par insertion frontale
Essayez-le sur GfG Practice 
C++
Sortir
Sortir
Sortir
Étant donné une chaîne s composée uniquement de lettres anglaises minuscules, trouvez le minimum nombre de caractères qui doivent être ajouté au devant de s pour en faire un palindrome.
Note: Un palindrome est une chaîne qui lit la même chose vers l'avant et vers l'arrière.
Exemples :
Saisir : s = 'abc'
Sortir : 2
Explication : Nous pouvons créer un palindrome de chaîne ci-dessus sous la forme 'cbabc' en ajoutant 'b' et 'c' devant.Saisir : s = 'aacecaaaa'
Sortir : 2
Explication : Nous pouvons créer le palindrome de la chaîne ci-dessus sous la forme 'aaaacecaaaa' en ajoutant deux a devant la chaîne.
Table des matières
- [Approche naïve] Vérification de tous les préfixes - O(n^2) Time et O(1) Space
- [Approche attendue 1] Utilisation du tableau lps de l'algorithme KMP - O(n) Time et O(n) Space
- [Approche attendue 2] Utilisation de l'algorithme de Manacher
[Approche naïve] Vérification de tous les préfixes - O(n^2) Time et O(1) Space
L'idée est basée sur l'observation selon laquelle nous devons trouver le préfixe le plus long d'une chaîne donnée qui est également un palindrome. Ensuite, le nombre minimum de caractères avant à ajouter pour créer un palindrome de chaîne donné sera les caractères restants.
C++ #include using namespace std ; // function to check if the substring s[i...j] is a palindrome bool isPalindrome ( string & s int i int j ) { while ( i < j ) { // if characters at the ends are not equal // it's not a palindrome if ( s [ i ] != s [ j ]) { return false ; } i ++ ; j -- ; } return true ; } int minChar ( string & s ) { int cnt = 0 ; int i = s . size () - 1 ; // iterate from the end of the string checking for the // longestpalindrome starting from the beginning while ( i >= 0 && ! isPalindrome ( s 0 i )) { i -- ; cnt ++ ; } return cnt ; } int main () { string s = 'aacecaaaa' ; cout < < minChar ( s ); return 0 ; }
C #include #include #include // function to check if the substring s[i...j] is a palindrome bool isPalindrome ( char s [] int i int j ) { while ( i < j ) { // if characters at the ends are not the same // it's not a palindrome if ( s [ i ] != s [ j ]) { return false ; } i ++ ; j -- ; } return true ; } int minChar ( char s []) { int cnt = 0 ; int i = strlen ( s ) - 1 ; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while ( i >= 0 && ! isPalindrome ( s 0 i )) { i -- ; cnt ++ ; } return cnt ; } int main () { char s [] = 'aacecaaaa' ; printf ( '%d' minChar ( s )); return 0 ; }
Java class GfG { // function to check if the substring // s[i...j] is a palindrome static boolean isPalindrome ( String s int i int j ) { while ( i < j ) { // if characters at the ends are not the same // it's not a palindrome if ( s . charAt ( i ) != s . charAt ( j )) { return false ; } i ++ ; j -- ; } return true ; } static int minChar ( String s ) { int cnt = 0 ; int i = s . length () - 1 ; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while ( i >= 0 && ! isPalindrome ( s 0 i )) { i -- ; cnt ++ ; } return cnt ; } public static void main ( String [] args ) { String s = 'aacecaaaa' ; System . out . println ( minChar ( s )); } }
Python # function to check if the substring s[i...j] is a palindrome def isPalindrome ( s i j ): while i < j : # if characters at the ends are not the same # it's not a palindrome if s [ i ] != s [ j ]: return False i += 1 j -= 1 return True def minChar ( s ): cnt = 0 i = len ( s ) - 1 # iterate from the end of the string checking for the # longest palindrome starting from the beginning while i >= 0 and not isPalindrome ( s 0 i ): i -= 1 cnt += 1 return cnt if __name__ == '__main__' : s = 'aacecaaaa' print ( minChar ( s ))
C# using System ; class GfG { // function to check if the substring s[i...j] is a palindrome static bool isPalindrome ( string s int i int j ) { while ( i < j ) { // if characters at the ends are not the same // it's not a palindrome if ( s [ i ] != s [ j ]) { return false ; } i ++ ; j -- ; } return true ; } static int minChar ( string s ) { int cnt = 0 ; int i = s . Length - 1 ; // iterate from the end of the string checking for the longest // palindrome starting from the beginning while ( i >= 0 && ! isPalindrome ( s 0 i )) { i -- ; cnt ++ ; } return cnt ; } static void Main () { string s = 'aacecaaaa' ; Console . WriteLine ( minChar ( s )); } }
JavaScript // function to check if the substring s[i...j] is a palindrome function isPalindrome ( s i j ) { while ( i < j ) { // if characters at the ends are not the same // it's not a palindrome if ( s [ i ] !== s [ j ]) { return false ; } i ++ ; j -- ; } return true ; } function minChar ( s ) { let cnt = 0 ; let i = s . length - 1 ; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while ( i >= 0 && ! isPalindrome ( s 0 i )) { i -- ; cnt ++ ; } return cnt ; } // Driver code let s = 'aacecaaaa' ; console . log ( minChar ( s ));
Sortir
2
[Approche attendue 1] Utilisation du tableau lps de l'algorithme KMP - O(n) Time et O(n) Space
L’observation clé est que le préfixe palindromique le plus long d’une chaîne devient le suffixe palindromique le plus long de son revers.
Étant donné une chaîne s = 'aacecaaaa', son inverse revS = 'aaaacecaa'. Le préfixe palindromique le plus long de s est « aacecaa ».
Pour trouver cela efficacement, nous utilisons le tableau LPS du Algorithme KMP . Nous concaténons la chaîne d'origine avec un caractère spécial et son inverse : s + '$' + revS.
Le tableau LPS pour cette chaîne combinée permet d'identifier le préfixe le plus long de s qui correspond à un suffixe de revS qui représente également le préfixe palindromique de s.
La dernière valeur du tableau LPS nous indique combien de caractères forment déjà un palindrome au début. Ainsi, le nombre minimum de caractères à ajouter pour faire de s un palindrome est s.length() - lps.back().
C++ #include #include #include using namespace std ; vector < int > computeLPSArray ( string & pat ) { int n = pat . length (); vector < int > lps ( n ); // lps[0] is always 0 lps [ 0 ] = 0 ; int len = 0 ; // loop calculates lps[i] for i = 1 to M-1 int i = 1 ; while ( i < n ) { // if the characters match increment len // and set lps[i] if ( pat [ i ] == pat [ len ]) { len ++ ; lps [ i ] = len ; i ++ ; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if ( len != 0 ) { len = lps [ len - 1 ]; } // no prefix matches set lps[i] to 0 else { lps [ i ] = 0 ; i ++ ; } } } return lps ; } // returns minimum character to be added at // front to make string palindrome int minChar ( string & s ) { int n = s . length (); string rev = s ; reverse ( rev . begin () rev . end ()); // get concatenation of string special character // and reverse string s = s + '$' + rev ; // get LPS array of this concatenated string vector < int > lps = computeLPSArray ( s ); // by subtracting last entry of lps vector from // string length we will get our result return ( n - lps . back ()); } int main () { string s = 'aacecaaaa' ; cout < < minChar ( s ); return 0 ; }
Java import java.util.ArrayList ; class GfG { static int [] computeLPSArray ( String pat ) { int n = pat . length (); int [] lps = new int [ n ] ; // lps[0] is always 0 lps [ 0 ] = 0 ; int len = 0 ; // loop calculates lps[i] for i = 1 to n-1 int i = 1 ; while ( i < n ) { // if the characters match increment len // and set lps[i] if ( pat . charAt ( i ) == pat . charAt ( len )) { len ++ ; lps [ i ] = len ; i ++ ; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if ( len != 0 ) { len = lps [ len - 1 ] ; } // no prefix matches set lps[i] to 0 else { lps [ i ] = 0 ; i ++ ; } } } return lps ; } // returns minimum character to be added at // front to make string palindrome static int minChar ( String s ) { int n = s . length (); String rev = new StringBuilder ( s ). reverse (). toString (); // get concatenation of string special character // and reverse string s = s + '$' + rev ; // get LPS array of this concatenated string int [] lps = computeLPSArray ( s ); // by subtracting last entry of lps array from // string length we will get our result return ( n - lps [ lps . length - 1 ] ); } public static void main ( String [] args ) { String s = 'aacecaaaa' ; System . out . println ( minChar ( s )); } }
Python def computeLPSArray ( pat ): n = len ( pat ) lps = [ 0 ] * n # lps[0] is always 0 len_lps = 0 # loop calculates lps[i] for i = 1 to n-1 i = 1 while i < n : # if the characters match increment len # and set lps[i] if pat [ i ] == pat [ len_lps ]: len_lps += 1 lps [ i ] = len_lps i += 1 # if there is a mismatch else : # if len is not zero update len to # the last known prefix length if len_lps != 0 : len_lps = lps [ len_lps - 1 ] # no prefix matches set lps[i] to 0 else : lps [ i ] = 0 i += 1 return lps # returns minimum character to be added at # front to make string palindrome def minChar ( s ): n = len ( s ) rev = s [:: - 1 ] # get concatenation of string special character # and reverse string s = s + '$' + rev # get LPS array of this concatenated string lps = computeLPSArray ( s ) # by subtracting last entry of lps array from # string length we will get our result return n - lps [ - 1 ] if __name__ == '__main__' : s = 'aacecaaaa' print ( minChar ( s ))
C# using System ; class GfG { static int [] computeLPSArray ( string pat ) { int n = pat . Length ; int [] lps = new int [ n ]; // lps[0] is always 0 lps [ 0 ] = 0 ; int len = 0 ; // loop calculates lps[i] for i = 1 to n-1 int i = 1 ; while ( i < n ) { // if the characters match increment len // and set lps[i] if ( pat [ i ] == pat [ len ]) { len ++ ; lps [ i ] = len ; i ++ ; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if ( len != 0 ) { len = lps [ len - 1 ]; } // no prefix matches set lps[i] to 0 else { lps [ i ] = 0 ; i ++ ; } } } return lps ; } // minimum character to be added at // front to make string palindrome static int minChar ( string s ) { int n = s . Length ; char [] charArray = s . ToCharArray (); Array . Reverse ( charArray ); string rev = new string ( charArray ); // get concatenation of string special character // and reverse string s = s + '$' + rev ; // get LPS array of this concatenated string int [] lps = computeLPSArray ( s ); // by subtracting last entry of lps array from // string length we will get our result return n - lps [ lps . Length - 1 ]; } static void Main () { string s = 'aacecaaaa' ; Console . WriteLine ( minChar ( s )); } }
JavaScript function computeLPSArray ( pat ) { let n = pat . length ; let lps = new Array ( n ). fill ( 0 ); // lps[0] is always 0 let len = 0 ; // loop calculates lps[i] for i = 1 to n-1 let i = 1 ; while ( i < n ) { // if the characters match increment len // and set lps[i] if ( pat [ i ] === pat [ len ]) { len ++ ; lps [ i ] = len ; i ++ ; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if ( len !== 0 ) { len = lps [ len - 1 ]; } // no prefix matches set lps[i] to 0 else { lps [ i ] = 0 ; i ++ ; } } } return lps ; } // returns minimum character to be added at // front to make string palindrome function minChar ( s ) { let n = s . length ; let rev = s . split ( '' ). reverse (). join ( '' ); // get concatenation of string special character // and reverse string s = s + '$' + rev ; // get LPS array of this concatenated string let lps = computeLPSArray ( s ); // by subtracting last entry of lps array from // string length we will get our result return n - lps [ lps . length - 1 ]; } // Driver Code let s = 'aacecaaaa' ; console . log ( minChar ( s ));
Sortir
2
[Approche attendue 2] Utilisation de l'algorithme de Manacher
C++L'idée est d'utiliser L'algorithme de Manacher pour trouver efficacement toutes les sous-chaînes palindromiques en temps linéaire.
Nous transformons la chaîne en insérant des caractères spéciaux (#) pour gérer uniformément les palindromes de longueur paire et impaire.
Après le prétraitement, nous parcourons à partir de la fin de la chaîne d'origine et utilisons le tableau de rayon palindrome pour vérifier si le préfixe s[0...i] est un palindrome. Le premier de ces index i nous donne le préfixe palindromique le plus long et nous renvoyons n - (i + 1) comme nombre minimum de caractères à ajouter.
#include #include #include using namespace std ; // manacher's algorithm for finding longest // palindromic substrings class manacher { public : // array to store palindrome lengths centered // at each position vector < int > p ; // modified string with separators and sentinels string ms ; manacher ( string & s ) { ms = '@' ; for ( char c : s ) { ms += '#' + string ( 1 c ); } ms += '#$' ; runManacher (); } // core Manacher's algorithm void runManacher () { int n = ms . size (); p . assign ( n 0 ); int l = 0 r = 0 ; for ( int i = 1 ; i < n - 1 ; ++ i ) { if ( i < r ) p [ i ] = min ( r - i p [ r + l - i ]); // expand around the current center while ( ms [ i + 1 + p [ i ]] == ms [ i - 1 - p [ i ]]) ++ p [ i ]; // update center if palindrome goes beyond // current right boundary if ( i + p [ i ] > r ) { l = i - p [ i ]; r = i + p [ i ]; } } } // returns the length of the longest palindrome // centered at given position int getLongest ( int cen int odd ) { int pos = 2 * cen + 2 + ! odd ; return p [ pos ]; } // checks whether substring s[l...r] is a palindrome bool check ( int l int r ) { int len = r - l + 1 ; int longest = getLongest (( l + r ) / 2 len % 2 ); return len <= longest ; } }; // returns the minimum number of characters to add at the // front to make the given string a palindrome int minChar ( string & s ) { int n = s . size (); manacher m ( s ); // scan from the end to find the longest // palindromic prefix for ( int i = n - 1 ; i >= 0 ; -- i ) { if ( m . check ( 0 i )) return n - ( i + 1 ); } return n - 1 ; } int main () { string s = 'aacecaaaa' ; cout < < minChar ( s ) < < endl ; return 0 ; }
Java class GfG { // manacher's algorithm for finding longest // palindromic substrings static class manacher { // array to store palindrome lengths centered // at each position int [] p ; // modified string with separators and sentinels String ms ; manacher ( String s ) { StringBuilder sb = new StringBuilder ( '@' ); for ( char c : s . toCharArray ()) { sb . append ( '#' ). append ( c ); } sb . append ( '#$' ); ms = sb . toString (); runManacher (); } // core Manacher's algorithm void runManacher () { int n = ms . length (); p = new int [ n ] ; int l = 0 r = 0 ; for ( int i = 1 ; i < n - 1 ; ++ i ) { if ( i < r ) p [ i ] = Math . min ( r - i p [ r + l - i ] ); // expand around the current center while ( ms . charAt ( i + 1 + p [ i ] ) == ms . charAt ( i - 1 - p [ i ] )) p [ i ]++ ; // update center if palindrome goes beyond // current right boundary if ( i + p [ i ] > r ) { l = i - p [ i ] ; r = i + p [ i ] ; } } } // returns the length of the longest palindrome // centered at given position int getLongest ( int cen int odd ) { int pos = 2 * cen + 2 + ( odd == 0 ? 1 : 0 ); return p [ pos ] ; } // checks whether substring s[l...r] is a palindrome boolean check ( int l int r ) { int len = r - l + 1 ; int longest = getLongest (( l + r ) / 2 len % 2 ); return len <= longest ; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome static int minChar ( String s ) { int n = s . length (); manacher m = new manacher ( s ); // scan from the end to find the longest // palindromic prefix for ( int i = n - 1 ; i >= 0 ; -- i ) { if ( m . check ( 0 i )) return n - ( i + 1 ); } return n - 1 ; } public static void main ( String [] args ) { String s = 'aacecaaaa' ; System . out . println ( minChar ( s )); } }
Python # manacher's algorithm for finding longest # palindromic substrings class manacher : # array to store palindrome lengths centered # at each position def __init__ ( self s ): # modified string with separators and sentinels self . ms = '@' for c in s : self . ms += '#' + c self . ms += '#$' self . p = [] self . runManacher () # core Manacher's algorithm def runManacher ( self ): n = len ( self . ms ) self . p = [ 0 ] * n l = r = 0 for i in range ( 1 n - 1 ): if i < r : self . p [ i ] = min ( r - i self . p [ r + l - i ]) # expand around the current center while self . ms [ i + 1 + self . p [ i ]] == self . ms [ i - 1 - self . p [ i ]]: self . p [ i ] += 1 # update center if palindrome goes beyond # current right boundary if i + self . p [ i ] > r : l = i - self . p [ i ] r = i + self . p [ i ] # returns the length of the longest palindrome # centered at given position def getLongest ( self cen odd ): pos = 2 * cen + 2 + ( 0 if odd else 1 ) return self . p [ pos ] # checks whether substring s[l...r] is a palindrome def check ( self l r ): length = r - l + 1 longest = self . getLongest (( l + r ) // 2 length % 2 ) return length <= longest # returns the minimum number of characters to add at the # front to make the given string a palindrome def minChar ( s ): n = len ( s ) m = manacher ( s ) # scan from the end to find the longest # palindromic prefix for i in range ( n - 1 - 1 - 1 ): if m . check ( 0 i ): return n - ( i + 1 ) return n - 1 if __name__ == '__main__' : s = 'aacecaaaa' print ( minChar ( s ))
C# using System ; class GfG { // manacher's algorithm for finding longest // palindromic substrings class manacher { // array to store palindrome lengths centered // at each position public int [] p ; // modified string with separators and sentinels public string ms ; public manacher ( string s ) { ms = '@' ; foreach ( char c in s ) { ms += '#' + c ; } ms += '#$' ; runManacher (); } // core Manacher's algorithm void runManacher () { int n = ms . Length ; p = new int [ n ]; int l = 0 r = 0 ; for ( int i = 1 ; i < n - 1 ; ++ i ) { if ( i < r ) p [ i ] = Math . Min ( r - i p [ r + l - i ]); // expand around the current center while ( ms [ i + 1 + p [ i ]] == ms [ i - 1 - p [ i ]]) p [ i ] ++ ; // update center if palindrome goes beyond // current right boundary if ( i + p [ i ] > r ) { l = i - p [ i ]; r = i + p [ i ]; } } } // returns the length of the longest palindrome // centered at given position public int getLongest ( int cen int odd ) { int pos = 2 * cen + 2 + ( odd == 0 ? 1 : 0 ); return p [ pos ]; } // checks whether substring s[l...r] is a palindrome public bool check ( int l int r ) { int len = r - l + 1 ; int longest = getLongest (( l + r ) / 2 len % 2 ); return len <= longest ; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome static int minChar ( string s ) { int n = s . Length ; manacher m = new manacher ( s ); // scan from the end to find the longest // palindromic prefix for ( int i = n - 1 ; i >= 0 ; -- i ) { if ( m . check ( 0 i )) return n - ( i + 1 ); } return n - 1 ; } static void Main () { string s = 'aacecaaaa' ; Console . WriteLine ( minChar ( s )); } }
JavaScript // manacher's algorithm for finding longest // palindromic substrings class manacher { // array to store palindrome lengths centered // at each position constructor ( s ) { // modified string with separators and sentinels this . ms = '@' ; for ( let c of s ) { this . ms += '#' + c ; } this . ms += '#$' ; this . p = []; this . runManacher (); } // core Manacher's algorithm runManacher () { const n = this . ms . length ; this . p = new Array ( n ). fill ( 0 ); let l = 0 r = 0 ; for ( let i = 1 ; i < n - 1 ; ++ i ) { if ( i < r ) this . p [ i ] = Math . min ( r - i this . p [ r + l - i ]); // expand around the current center while ( this . ms [ i + 1 + this . p [ i ]] === this . ms [ i - 1 - this . p [ i ]]) this . p [ i ] ++ ; // update center if palindrome goes beyond // current right boundary if ( i + this . p [ i ] > r ) { l = i - this . p [ i ]; r = i + this . p [ i ]; } } } // returns the length of the longest palindrome // centered at given position getLongest ( cen odd ) { const pos = 2 * cen + 2 + ( odd === 0 ? 1 : 0 ); return this . p [ pos ]; } // checks whether substring s[l...r] is a palindrome check ( l r ) { const len = r - l + 1 ; const longest = this . getLongest ( Math . floor (( l + r ) / 2 ) len % 2 ); return len <= longest ; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome function minChar ( s ) { const n = s . length ; const m = new manacher ( s ); // scan from the end to find the longest // palindromic prefix for ( let i = n - 1 ; i >= 0 ; -- i ) { if ( m . check ( 0 i )) return n - ( i + 1 ); } return n - 1 ; } // Driver Code const s = 'aacecaaaa' ; console . log ( minChar ( s ));
Sortir
2
Complexité temporelle : L'algorithme de O(n) Manacher s'exécute en temps linéaire en développant les palindromes à chaque centre sans revisiter les caractères et la boucle de vérification des préfixes effectue des opérations O(1) par caractère sur n caractères.
Espace auxiliaire : O(n) utilisé pour la chaîne modifiée et le tableau de longueur du palindrome p[], qui croissent tous deux linéairement avec la taille d'entrée.
