समस्या विवरण
मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें s का सबसे लंबा हैप्पी प्रीफिक्स ढूंढना है। एक स्ट्रिंग को हैप्पी प्रीफिक्स कहा जाता है यदि यह एक गैर-खाली प्रीफिक्स है जो एक सफिक्स भी है (स्वयं को छोड़कर)। यदि ऐसा कोई हैप्पी प्रीफिक्स नहीं है, तो बस खाली स्ट्रिंग लौटाएं।
उदाहरण
यदि इनपुट है: "madam", तो आउटपुट होगा "m", इसके 4 प्रीफिक्स हैं स्वयं को छोड़कर। ये हैं "m", "ma", "mad", "mada" और 4 सफिक्स जैसे "m", "am", "dam", "adam"। सबसे बड़ा प्रीफिक्स जो सफिक्स भी है, वह "m" द्वारा दिया गया है।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (KMP एल्गोरिदम का LPS सरणी):
- lps() नामक एक फ़ंक्शन परिभाषित करें, जो s लेता है:
- n := s का आकार
- आकार n की एक सरणी ret परिभाषित करें
- j := 0, i := 1
- जब i < n:
- यदि s[i], s[j] के समान है:
- ret[i] := j + 1
- i को 1 से बढ़ाएं
- j को 1 से बढ़ाएं
- अन्यथा जब s[i], s[j] के बराबर नहीं है:
- यदि j > 0:
- j := ret[j - 1]
- अन्यथा:
- i को 1 से बढ़ाएं
- यदि j > 0:
- यदि s[i], s[j] के समान है:
- ret लौटाएं
- मुख्य विधि से:
- n := s का आकार
- यदि n, 1 के समान है, तो खाली स्ट्रिंग लौटाएं
- v := lps(s)
- x := v[n - 1]
- ret := खाली स्ट्रिंग
- i := 0 से आरंभ करें, जब i < x, i को 1 से बढ़ाते हुए:
- ret := ret + s[i]
- ret लौटाएं
C++ कार्यान्वयन
#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;
}
};
int main() {
Solution ob;
cout << (ob.longestPrefix("madam"));
return 0;
}
इनपुट
"madam"
आउटपुट
m