C++ এ সবচেয়ে ছোট প্যালিনড্রোম

ধরুন আমরা একটি স্ট্রিং s আছে. আমরা এর সামনে অক্ষর যোগ করে এটিকে প্যালিনড্রোমে রূপান্তর করতে পারি। আমরা সংক্ষিপ্ত প্যালিনড্রোম খুঁজে বের করতে হবে, যে আমরা এই তথ্য সম্পাদন করতে পারেন. সুতরাং যদি স্ট্রিংটি "abcc" এর মত হয়, তাহলে ফলাফল হবে − "ccbabcc"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=s, s1 :=s, s2 :=s

  এর আকার

• স্ট্রিং s2 বিপরীত করুন

• s2 :=s concatenate "#" concatenate 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 দ্বারা বাড়ান

• অতিরিক্ত :=s-এর সাবস্ট্রিং lps[s-1] থেকে n - lps[lps-এর আকার - 1])

• বিপরীত অতিরিক্ত

• অতিরিক্ত কনক্যাটেনেট ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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