मान लीजिए कि हमारे पास एक स्ट्रिंग s है। हम इसके सामने अक्षर जोड़कर इसे पैलिंड्रोम में बदल सकते हैं। हमें सबसे छोटा पैलिंड्रोम खोजना होगा, जिससे हम इस जानकारी को निष्पादित करते हुए पा सकें। तो अगर स्ट्रिंग "abcc" की तरह है, तो परिणाम होगा - "ccbabcc"।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=s का आकार, s1 :=s, s2 :=s
-
स्ट्रिंग s2 को उल्टा करें
-
s2 :=s concatenate "#" concatenate s2
-
s2 के समान आकार की एक सरणी lps परिभाषित करें
-
जे:=0, मैं:=1
-
जबकि मैं
-
अगर s2[i] s2[j] के समान है, तो,
-
एलपीएस[i] :=j + 1
-
1 से बढ़ाएँ, j को 1 से बढ़ाएँ
-
-
अन्यथा
-
अगर j> 0, तो, j :=lps[j-1]
-
अन्यथा i को 1 से बढ़ाएँ
-
-
-
अतिरिक्त:=एलपीएस से एस का सबस्ट्रिंग [एस - 1 का आकार] से एन - एलपीएस [एलपीएस का आकार - 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