C++ में सबसे लंबा प्रीफिक्स जो सफिक्स भी है ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें s का सबसे लंबा प्रीफिक्स ढूंढना है जो एक सफिक्स भी है (स्वयं को छोड़कर)। यदि ऐसा कोई प्रीफिक्स नहीं है, तो बस खाली स्ट्रिंग वापस करें।

उदाहरण के लिए, यदि इनपुट "madam" है, तो आउटपुट "m" होगा, इसके स्वयं को छोड़कर 4 प्रीफिक्स हैं। ये "m", "ma", "mad", "mada" हैं और 4 सफिक्स जैसे "m", "am", "dam", "adam" हैं। सबसे बड़ा प्रीफिक्स जो सफिक्स भी है, "m" द्वारा दिया जाता है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम KMP एल्गोरिदम के LPS (लॉन्गेस्ट प्रीफिक्स सफिक्स) ऐरे का उपयोग करेंगे:

1. एक फंक्शन lps() परिभाषित करें जो s लेता है
2. n := s का आकार
3. आकार n का एक ऐरे ret परिभाषित करें
4. j := 0, i := 1
5. जब तक i < n:
   • यदि s[i] == s[j], तो ret[i] := j+1, i++, j++
   • अन्यथा जब s[i] != s[j]:
     • यदि j > 0, तो j := ret[j-1]
     • अन्यथा i++
6. ret वापस करें
7. मुख्य विधि से:
   • n := s का आकार
   • यदि n == 1, तो खाली स्ट्रिंग वापस करें
   • v = lps(s)
   • x := v[n-1]
   • ret := खाली स्ट्रिंग
   • i := 0 से x-1 तक: ret := ret + s[i]
   • ret वापस करें

उदाहरण

#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("helloworldhello"));
}

इनपुट

"helloworldhello"

आउटपुट

hello