logo

TechCodeview

前挿入による回文

GfG Practice で試してみる 回文の前に追加する文字' title=

英小文字のみで構成される文字列 s が与えられた場合、 最小 必要な文字数 追加した に フロント s を使って回文にします。
注記： 回文は、前から読んでも後ろから読んでも同じ文字列です。

例:  

入力 : s = 'abc'
出力 ：2
説明 : 上記の文字列の先頭に 'b' と 'c' を追加すると、'cbabc' として回文を作成できます。



入力 : s = 'アエースカアア'
出力 ：2
説明 : 文字列の前に 2 つの a を追加すると、上記の文字列回文を 'aaaacecaaaa' として作成できます。

目次

[単純なアプローチ] すべてのプレフィックスをチェックする - O(n^2) 時間と O(1) 空間

このアイデアは、回文でもある指定された文字列から最長のプレフィックスを見つける必要があるという観察に基づいています。この場合、指定された文字列回文を作成するために追加される最小の先頭文字が残りの文字になります。

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

出力 
2

【想定されるアプローチ1】KMPアルゴリズムのlps配列を利用する - 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】Manacherのアルゴリズムを利用する

アイデアは使用することです マナハのアルゴリズム すべての回文部分文字列を線形時間で効率的に見つけることができます。
特殊文字 (#) を挿入して文字列を変換し、偶数長と奇数長の両方の回文を均一に処理します。
前処理の後、元の文字列の末尾からスキャンし、回文半径配列を使用して接頭辞 s[0...i] が回文であるかどうかを確認します。最初のそのようなインデックス i は最長の回文接頭辞を与え、追加する最小文字として n - (i + 1) を返します。

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

出力 
2

時間計算量: O(n) manacher のアルゴリズムは、文字を再訪することなく各中心で回文を展開することで線形時間で実行され、プレフィックス チェック ループは n 文字にわたって文字ごとに O(1) 操作を実行します。
補助スペース: 変更された文字列と回文の長さの配列 p[] に使用される O(n) は、どちらも入力サイズに応じて線形に増加します。

クイズの作成