একটি স্ট্রিং s দেওয়া আছে। এর লংগেস্ট হ্যাপি প্রিফিক্স বের করুন। হ্যাপি প্রিফিক্স = নন-এমপটি প্রিফিক্স যা সাফিক্সও (নিজের বাদে)। না থাকলে খালি স্ট্রিং।
উদাহরণ: "madam" -> "m"। প্রিফিক্স: m, ma, mad, mada। সাফিক্স: m, am, dam, adam। সাধারণ সর্বোচ্চ "m"।
সমাধানের ধাপসমূহ
- KMP LPS (Longest Prefix Suffix) অ্যারে বানান।
- lps(s): n = s.size(), ret[n], j=0, i=1।
- যদি s[i]==s[j]: ret[i]=j+1; i++; j++।
- অন্যথায়: j>0 হলে j=ret[j-1], অন্যথায় i++।
- x = ret[n-1]। s[0..x-1] রিটার্ন করুন।
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, 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
