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