logo

TechCodeview

Palindrome elülső beillesztéssel

Próbáld ki a GfG Practice-n a Palindrome elejére feladandó karakterek' title=

Adott egy s karakterlánc, amely csak kisbetűket tartalmaz angolul, találja meg a minimális a szükséges karakterek száma tette hozzá a elülső az s hogy palindrommá tegye.
Jegyzet: A palindrom egy olyan karakterlánc, amely ugyanazt olvassa előre és hátra.

Példák:  

jquery szülő

Bemenet : s = 'abc'
Kimenet : 2
Magyarázat : A fenti string palindromot 'cbabc'-ként állíthatjuk elő, ha a 'b'-t és a 'c'-t adjuk hozzá.



Bemenet : s = 'aacecaaaa'
Kimenet : 2
Magyarázat : A fenti string palindromot 'aaaacecaaaa'-ként állíthatjuk elő, ha a karakterlánc elé két a-t adunk.

globális var a js-ben

Tartalomjegyzék

[Naiv megközelítés] Az összes előtag ellenőrzése – O(n^2) idő és O(1) tér

Az ötlet azon a megfigyelésen alapul, hogy meg kell találnunk a leghosszabb előtagot az adott karakterláncból, amely egyben palindrom is. Ekkor az adott string palindrom létrehozásához hozzáadandó minimális elülső karakterek lesznek a fennmaradó karakterek.

' title= 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));

Kimenet 
2

[1. elvárt megközelítés] KMP algoritmus lps tömbjének használata - O(n) idő és O(n) tér

A legfontosabb megfigyelés az, hogy egy húr leghosszabb palindrom előtagja a hátoldalának leghosszabb palindrom utótagja lesz.
Adott egy s = 'aacecaaaa' karakterlánc, annak fordított revS = 'aaaacecaa'. Az s leghosszabb palindrom előtagja az „aacecaa”.

Ennek hatékony megtalálásához használjuk az LPS tömböt a KMP algoritmus . Az eredeti karakterláncot összefűzzük egy speciális karakterrel és a fordítottjával: s + '$' + revS.
A kombinált karakterlánc LPS-tömbje segít azonosítani az s leghosszabb előtagját, amely megegyezik a revS utótagjával, amely egyben az s palindrom előtagját is képviseli.

Az LPS tömb utolsó értéke megmondja, hogy hány karakter alkot már az elején palindromot. Így az s.length() - lps.back() karakterek minimális száma ahhoz, hogy s.length() - lps.back().

sor és oszlop
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));

Kimenet 
2

[2. elvárt megközelítés] Manacher algoritmusának használata

Az ötlet az, hogy használjuk Manacher algoritmusa hogy hatékonyan megtalálja az összes palindrom részstringet lineáris időben.
A karakterláncot speciális karakterek (#) beszúrásával alakítjuk át, hogy a páros és páratlan hosszúságú palindromokat is egységesen kezeljük.
Az előfeldolgozás után az eredeti karakterlánc végétől szkennelünk, és a palindrom sugarú tömb segítségével ellenőrizzük, hogy az s[0...i] előtag palindrom-e. Az első ilyen i index megadja a leghosszabb palindrom előtagot, és az n - (i + 1) értéket adjuk vissza minimális hozzáadandó karakterként.

C++ 
#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));

Kimenet 
2

Időbeli összetettség: Az O(n) menedzser algoritmusa lineáris időben fut a palindromok kibontásával az egyes központokban a karakterek újralátogatása nélkül, és az előtag-ellenőrző hurok karakterenként O(1) műveletet hajt végre n karakter felett.
Kiegészítő tér: A módosított karakterlánchoz és a p[] palindromhosszúságú tömbhöz használt O(n) lineárisan nő a bemeneti mérettel.

Kvíz létrehozása