logo

TechCodeview

Palindrom ved frontinnsetting

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

Gitt en streng s som kun består av små engelske bokstaver, finn den minimum antall tegn som må være lagt til til front av s for å gjøre det til et palindrom.
Note: Et palindrom er en streng som leser det samme fremover og bakover.

Eksempler:  

Inndata : s = 'abc'
Produksjon : 2
Forklaring : Vi kan lage strengpalindrom over som 'cbabc' ved å legge til 'b' og 'c' foran.



Inndata : s = 'aacecaaaa'
Produksjon : 2
Forklaring : Vi kan lage strengpalindrom over som 'aaaacecaaaa' ved å legge til to a-er foran strengen.

Innholdsfortegnelse

[Naiv tilnærming] Kontrollerer alle prefikser - O(n^2) Tid og O(1) Mellomrom

Ideen er basert på observasjonen at vi må finne det lengste prefikset fra gitt streng som også er et palindrom. Da vil minimum fronttegn som skal legges til for å lage gitt strengpalindrom være de resterende tegnene.

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

Produksjon 
2

[Forventet tilnærming 1] Bruke lps-array av KMP-algoritme - O(n) Tid og O(n) Space

Den viktigste observasjonen er at det lengste palindromiske prefikset til en streng blir det lengste palindromiske suffikset på baksiden.
Gitt en streng s = 'aacecaaaa' dens omvendte revS = 'aaaacecaa'. Det lengste palindromiske prefikset til s er 'aacecaa'.

For å finne dette effektivt bruker vi LPS-arrayet fra KMP algoritme . Vi setter sammen den opprinnelige strengen med et spesialtegn og dens omvendte: s + '$' + revS.
LPS-matrisen for denne kombinerte strengen hjelper til med å identifisere det lengste prefikset til s som samsvarer med et suffiks av revS som også representerer det palindromiske prefikset til s.

Den siste verdien av LPS-matrisen forteller oss hvor mange tegn som allerede danner et palindrom i begynnelsen. Dermed er minimum antall tegn som skal legges til for å gjøre s til et palindrom 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));

Produksjon 
2

[Forventet tilnærming 2] Bruke Manachers algoritme

Tanken er å bruke Manachers algoritme for å effektivt finne alle palindromiske delstrenger i lineær tid.
Vi transformerer strengen ved å sette inn spesialtegn (#) for å håndtere palindromer med både partall og oddetall jevnt.
Etter forbehandling skanner vi fra slutten av den originale strengen og bruker palindromradiusarrayen for å sjekke om prefikset s[0...i] er et palindrom. Den første slike indeks i gir oss det lengste palindromiske prefikset og vi returnerer n - (i + 1) som minimumstegn å legge til.

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

Produksjon 
2

Tidskompleksitet: O(n) manachers algoritme kjører i lineær tid ved å utvide palindromer ved hvert senter uten å gå tilbake til tegn, og prefikssjekksløyfen utfører O(1) operasjoner per tegn over n tegn.
Hjelpeplass: O(n) brukt for den modifiserte strengen og palindromlengde-arrayen p[] som begge vokser lineært med inngangsstørrelsen.

Lag quiz