Palindrome ngắn nhất trong C ++

Giả sử chúng ta có một chuỗi s. Chúng ta có thể chuyển nó thành palindrome bằng cách thêm các ký tự vào trước nó. Chúng tôi phải tìm palindrome ngắn nhất mà chúng tôi có thể tìm thấy khi thực hiện thông tin này. Vì vậy, nếu chuỗi giống như "abcc", thì kết quả sẽ là - "ccbabcc".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, s1:=s, s2:=s

• Đảo ngược chuỗi s2

• s2:=s nối "#" nối s2

• Xác định một mảng có kích thước lps giống như s2

• j:=0, i:=1

• while i

  • nếu s2 [i] giống với s2 [j] thì

    • lps [i]:=j + 1

    • tăng i lên 1, tăng j thêm 1

  • Nếu không

    • nếu j> 0, thì j:=lps [j - 1]

    • Nếu không, hãy tăng tôi lên 1

• extra:=chuỗi con của s từ lps [size of s - 1] đến n - lps [size of lps - 1])

• Đảo ngược bổ sung

• trả về nối thêm s

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

“abcc”

Đầu ra

ccbabcc