मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें s का सबसे लंबा हैप्पी प्रीफ़िक्स ढूंढना है। एक स्ट्रिंग को एक खुश उपसर्ग कहा जाता है यदि एक गैर-रिक्त उपसर्ग है जो एक प्रत्यय भी है (स्वयं को छोड़कर)। यदि ऐसा कोई हैप्पी उपसर्ग नहीं है, तो बस रिक्त स्ट्रिंग लौटाएं।
इसलिए, यदि इनपुट "मैडम" जैसा है, तो आउटपुट "m" होगा, इसमें स्वयं को छोड़कर 4 उपसर्ग हैं। ये "म", "मा", "मैड", "माडा" और "एम", "एम", "डैम", "एडम" जैसे 4 प्रत्यय हैं। सबसे बड़ा उपसर्ग जो प्रत्यय भी होता है वह "m" द्वारा दिया जाता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन lps () को परिभाषित करें, इसमें s लगेंगे,
-
n :=s का आकार
-
आकार n के सरणी रिट को परिभाषित करें
-
जे:=0, मैं:=1
-
जबकि मैं
-
यदि s[i], s[j] के समान है, तो
-
रिट[i] :=j + 1
-
(मैं 1 से बढ़ाइए)
-
(जम्मू को 1 से बढ़ाएं)
-
-
अन्यथा जब s[i] s[j] के बराबर नहीं है, तो -
-
अगर j> 0, तो -
-
जे:=रिट [जे -1]
-
-
अन्यथा
-
(मैं 1 से बढ़ाइए)
-
-
-
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
n :=s का आकार
-
यदि n 1 के समान है, तो -
-
रिक्त स्ट्रिंग लौटाएं
-
-
एक सरणी परिभाषित करें v =lps(s)
-
एक्स:=वी [एन -1]
-
रिट:=खाली स्ट्रिंग
-
इनिशियलाइज़ करने के लिए i:=0, जब i
-
रिट:=रिट + एस[i]
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <int> lps(string s){
int n = s.size();
vector<int> ret(n);
int j = 0;
int i = 1;
while (i < n) {
if (s[i] == s[j]) {
ret[i] = j + 1;
i++;
j++;
}
else if (s[i] != s[j]) {
if (j > 0)
j = ret[j - 1];
else {
i++;
}
}
}
return ret;
}
string longestPrefix(string s) {
int n = s.size();
if (n == 1)
return "";
vector<int> v = lps(s);
int x = v[n - 1];
string ret = "";
for (int i = 0; i < x; i++) {
ret += s[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestPrefix("madam"));
} इनपुट
"madam"
आउटपुट
m