Паліндром шляхом передньої вставки
Спробуйте на GfG Practice 
C++
Вихід
Вихід
Вихід
Дано рядок s, який складається лише з малих літер англійської мови, знайдіть мінімум кількість символів, які повинні бути додано до спереду з s, щоб зробити його паліндромом.
Примітка: Паліндром — це рядок, який однаково читається вперед і назад.
приклади:
Введення : s = 'abc'
Вихід : 2
Пояснення : ми можемо зробити верхній паліндром рядка «cbabc», додавши «b» і «c» спереду.Введення : s = 'aacecaaaa'
Вихід : 2
Пояснення : ми можемо зробити паліндром над рядком у вигляді «aaaacecaaaa», додавши дві букви a перед рядком.
Зміст
- [Наївний підхід] Перевірка всіх префіксів - O(n^2) Час і O(1) Пробіл
- [Очікуваний підхід 1] Використання масиву lps алгоритму KMP – O(n) часу та O(n) простору
- [Очікуваний підхід 2] Використання алгоритму менеджера
[Наївний підхід] Перевірка всіх префіксів - O(n^2) Час і O(1) Пробіл
Ідея заснована на спостереженні, що нам потрібно знайти найдовший префікс із заданого рядка, який також є паліндромом. Тоді мінімальні передні символи, які потрібно додати, щоб створити паліндром даного рядка, будуть символами, що залишилися.
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 ));
Вихід
2
[Очікуваний підхід 1] Використання масиву lps алгоритму KMP – O(n) часу та O(n) простору
Ключове спостереження полягає в тому, що найдовший паліндромний префікс рядка стає найдовшим паліндромним суфіксом його зворотного боку.
Дано рядок s = 'aacecaaaa', його зворотний revS = 'aaaacecaa'. Найдовшим паліндромним префіксом s є 'aacecaa'.
Щоб знайти це ефективно, ми використовуємо масив LPS з Алгоритм KMP . Ми об’єднуємо оригінальний рядок зі спеціальним символом і його зворотний: s + '$' + revS.
Масив LPS для цього комбінованого рядка допомагає ідентифікувати найдовший префікс s, який відповідає суфіксу revS, який також представляє паліндромний префікс s.
Останнє значення масиву LPS повідомляє нам, скільки символів уже утворюють паліндром на початку. Таким чином, мінімальна кількість символів, яку потрібно додати, щоб зробити s паліндромом, це 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 ));
Вихід
2
[Очікуваний підхід 2] Використання алгоритму менеджера
C++Ідея полягає в тому, щоб використовувати Алгоритм менеджера щоб ефективно знаходити всі паліндромні підрядки за лінійний час.
Ми перетворюємо рядок, вставляючи спеціальні символи (#), щоб однаково обробляти паліндроми парної та непарної довжини.
Після попередньої обробки ми скануємо з кінця оригінального рядка та використовуємо масив радіусів паліндрому, щоб перевірити, чи є префікс s[0...i] паліндромом. Перший такий індекс i дає нам найдовший паліндромний префікс, і ми повертаємо n - (i + 1) як мінімальну кількість символів для додавання.
#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 ));
Вихід
2
Часова складність: Алгоритм O(n) менеджера працює в лінійному часі, розширюючи паліндроми в кожному центрі без повторного перегляду символів, а цикл перевірки префіксів виконує O(1) операцій на символ над n символами.
Допоміжний простір: O(n), що використовується для зміненого рядка та масиву довжини паліндрому p[], обидва з яких лінійно зростають із розміром вхідних даних.
