Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसे लंबा हैप्पी प्रीफिक्स


समस्या विवरण

मान लीजिए हमारे पास एक स्ट्रिंग 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 से बढ़ाएं
    • 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
  1. - C++ में प्रीफिक्स से पोस्टफिक्स रूपांतरण

    इस समस्या में, हमें एक प्रीफिक्स एक्सप्रेशन दिया गया है। हमारा कार्य दिए गए एक्सप्रेशन का पोस्टफिक्स रूपांतरण प्रिंट करना है।प्रीफिक्स एक्सप्रेशन वे एक्सप्रेशन हैं जिनमें ऑपरेटर ऑपरेंड्स से पहले होते हैं।उदाहरण: +AB.पोस्टफिक्स एक्सप्रेशन वे एक्सप्रेशन हैं जिनमें ऑपरेटर एक्सप्रेशन में ऑपरेंड्स क

  1. - न्यूनतम शिफ्ट खोजें सबसे लंबे सामान्य उपसर्ग के लिए C++ में

    मान लीजिए हमारे पास दो स्ट्रिंग्स A और B हैं। A और B की लंबाई समान है। एक शिफ्ट में हम स्ट्रिंग B को एक तत्व घुमा सकते हैं। हमें न्यूनतम आवश्यक शिफ्ट खोजनी है ताकि A और B से अधिकतम लंबाई का सामान्य उपसर्ग मिल सके। तो यदि A = computerprogramming, और B = programminglanguage तो न्यूनतम शिफ्ट 8 है, और उ

  1. - C++ प्रोग्राम: दिए गए सीक्वेंस के सबसे लंबे प्रीफिक्स मैचिंग को खोजना

    यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो एक सेट ऑफ सीक्वेंस में सभी सीक्वेंस के लिए कॉमन सबसे लंबी सबसीक्वेंस खोजता है। एल्गोरिदम Begin स्ट्रिंग्स की ऐरे को इनपुट के रूप में लें। function matchedPrefixtill(): स्ट्रिंग s1 और s2 के बीच मैच्ड प्रीफिक्स खोजें: n1 = स्ट्रिंग s1 की लं