logo

TechCodeview

전면 삽입에 의한 회문

GfG Practice에서 사용해 보세요. Palindrome을 위해 앞에 추가할 문자' title=

영어 소문자로만 구성된 문자열 s가 주어지면 최저한의 필요한 문자 수 추가됨 에 앞쪽 s를 사용하여 회문으로 만듭니다.
메모: 회문은 앞으로 읽어도 뒤로 읽어도 같은 문자열입니다.

예:  

입력 : s = 'abc'
산출 : 2
설명 : 위 문자열 회문 앞에 'b'와 'c'를 추가하면 'cbabc'로 만들 수 있습니다.



입력 : s = '아아세카아아아'
산출 : 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'입니다.

자바의 char + int

이를 효율적으로 찾기 위해 우리는 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의 알고리즘을 활용

아이디어는 사용하는 것입니다 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)은 둘 다 입력 크기에 따라 선형적으로 증가합니다.

퀴즈 만들기