logo

TechCodeview

Palindrom ved frontindføring

Prøv det på GfG Practice tegn-til-føje-på-front-til-Palindrome' title=

Givet en streng s bestående af kun små engelske bogstaver find den minimum antal tegn, der skal være tilføjet til front af s for at gøre det til et palindrom.
Note: Et palindrom er en streng, der læser det samme frem og tilbage.

Eksempler:  

Input : s = 'abc'
Produktion : 2
Forklaring : Vi kan lave ovenstående strengpalindrom som 'cbabc' ved at tilføje 'b' og 'c' foran.



Input : s = 'aacecaaaa'
Produktion : 2
Forklaring : Vi kan lave ovenstående strengpalindrom som 'aaaacecaaaa' ved at tilføje to a'er foran på strengen.

Indholdsfortegnelse

[Naiv tilgang] Kontrollerer alle præfikser - O(n^2) Tid og O(1) Mellemrum

Ideen er baseret på den observation, at vi skal finde det længste præfiks fra en given streng, som også er et palindrom. Så vil minimum forreste tegn, der skal tilføjes for at lave en given strengpalindrom, være de resterende tegn.

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

Produktion 
2

[Forventet tilgang 1] Brug af lps-array af KMP-algoritme - O(n) tid og O(n) rum

Den vigtigste observation er, at det længste palindromiske præfiks af en streng bliver det længste palindromiske suffiks af dens bagside.
Givet en streng s = 'aacecaaaa' dens omvendte revS = 'aaaacecaa'. Det længste palindromiske præfiks af s er 'aacecaa'.

For at finde dette effektivt bruger vi LPS-arrayet fra KMP algoritme . Vi sammenkæder den oprindelige streng med et specialtegn og dets omvendte: s + '$' + revS.
LPS-arrayet for denne kombinerede streng hjælper med at identificere det længste præfiks af s, der matcher et suffiks af revS, som også repræsenterer det palindromiske præfiks af s.

Den sidste værdi af LPS-arrayet fortæller os, hvor mange tegn, der allerede danner et palindrom i begyndelsen. Det mindste antal tegn, der skal tilføjes for at gøre s til et palindrom, er således 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));

Produktion 
2

[Forventet tilgang 2] Brug af Manachers algoritme

Ideen er at bruge Manachers algoritme for effektivt at finde alle palindromiske understrenge i lineær tid.
Vi transformerer strengen ved at indsætte specialtegn (#) for at håndtere både lige og ulige længde palindromer ensartet.
Efter forbehandling scanner vi fra enden af ​​den originale streng og bruger palindromradius-arrayet til at kontrollere, om præfikset s[0...i] er et palindrom. Det første indeks i giver os det længste palindromiske præfiks, og vi returnerer n - (i + 1) som minimumstegn, der skal tilføjes.

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));

Produktion 
2

Tidskompleksitet: O(n) manachers algoritme kører i lineær tid ved at udvide palindromer i hvert center uden at gense tegn, og præfikset check loop udfører O(1) operationer pr. tegn over n tegn.
Hjælpeplads: O(n) brugt til den modificerede streng og palindromlængdearrayet p[] som begge vokser lineært med inputstørrelsen.

Opret quiz