সি++-এ স্ট্রিংয়ের সর্বোচ্চ প্রিফিক্স যা সাফিক্স ও আছে সেটি খুঁজে বের করা

সমস্যা বিবরণ

একটি স্ট্রিং s দেওয়া আছে। স্ট্রিংটির নিজের বাদে এমন সবচেয়ে বড় প্রিফিক্স খুঁজে বের করতে হবে যা সাফিক্সও হয়। না থাকলে খালি স্ট্রিং রিটার্ন করুন।

উদাহরণ: "madam" → আউটপুট "m"। প্রিফিক্স: m, ma, mad, mada; সাফিক্স: m, am, dam, adam।

সমাধানের পদ্ধতি

KMP অ্যালগরিদমের LPS (Longest Prefix Suffix) অ্যারে:

1. lps[i] = সাবস্ট্রিং s[0...i]-র সর্বোচ্চ প্রোপার প্রিফিক্স যা সাফিক্সও।
2. দুটি পয়েন্টার i, j দিয়ে লিনিয়ার টাইমে LPS বানান।
3. শেষে lps[n-1] দিয়ে প্রিফিক্সের লেন্থ পাওয়া যায়।
4. সাবস্ট্রিং s[0...lps[n-1]-1] রিটার্ন করুন।

উদাহরণ কোড

#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, i = 1;
        while (i < n) {
            if (s[i] == s[j]) { ret[i] = j + 1; i++; j++; }
            else 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");
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "helloworldhello"

আউটপুট: hello