C++에서 가장 짧은 회문

문자열 s가 있다고 가정합니다. 앞에 문자를 추가하여 회문으로 변환할 수 있습니다. 우리는 이 정보를 수행하면서 찾을 수 있는 가장 짧은 회문을 찾아야 합니다. 따라서 문자열이 "abcc"와 같으면 결과는 - "ccbabcc"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=s의 크기, s1 :=s, s2 :=s

• 문자열 s2를 뒤집습니다.

• s2 :=s 연결 "#" s2 연결

• s2와 동일한 크기의 배열 lps 정의

• j :=0, i :=1

• i

  • s2[i]가 s2[j]와 같으면

    • lps[i] :=j + 1

    • i 1 증가, j 1 증가

  • 그렇지 않으면

    • j> 0이면 j :=lps[j - 1]

    • 그렇지 않으면 i를 1만큼 증가

• extra :=lps[size of s – 1]에서 n - lps[size of lps - 1]까지의 s의 부분 문자열)

• 리버스 엑스트라

• 추가 연결 s를 반환합니다.

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string shortestPalindrome(string s) {
      int n = s.size();
      string s1 = s;
      string s2 = s;
      reverse(s2.begin(), s2.end());
      s2 = s + "#" + s2;
      vector <int> lps(s2.size());
      int j = 0;
      int i = 1;
      while(i <s2.size()){
         if(s2[i] == s2[j]){
            lps[i] = j + 1;
            j++;
            i++;
         } else {
            if(j > 0){
               j = lps[ j - 1];
            } else {
               i++;
            }
         }
      }
      string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]);
      reverse(extra.begin(), extra.end());
      return extra + s;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestPalindrome("abcc"));
}

입력

“abcc”

출력

ccbabcc