ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের s-এর দীর্ঘতম উপসর্গটি খুঁজে বের করতে হবে, যা একটি প্রত্যয়ও (নিজেকে বাদ দিয়ে)। যদি এমন কোন উপসর্গ না থাকে, তাহলে খালি স্ট্রিং ফেরত দিন।
সুতরাং, যদি ইনপুটটি "ম্যাডাম" এর মতো হয়, তবে আউটপুটটি হবে "m", এটিতে নিজেই বাদ দিয়ে 4টি উপসর্গ রয়েছে। এগুলি হল "ম", "মা", "পাগল", "মাদা" এবং "ম", "আম", "দাম", "আদাম" এর মতো 4টি প্রত্যয়। সবচেয়ে বড় উপসর্গ যা প্রত্যয়ও "m" দ্বারা দেওয়া হয়।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সংজ্ঞায়িত করুন lps(), এটি s,
লাগবে -
n :=s
এর আকার -
n
আকারের একটি অ্যারে রেট সংজ্ঞায়িত করুন -
j :=0, i :=1
-
যখন i
-
যদি s[i] s[j] এর মত হয়, তাহলে −
-
ret[i] :=j + 1
-
(i 1 দ্বারা বাড়ান)
-
(j 1 দ্বারা বাড়ান)
-
-
অন্যথায় যখন s[i] s[j] এর সমান না হয়, তখন −
-
যদি j> 0 হয়, তাহলে −
-
j :=ret[j − 1]
-
-
অন্যথায়
-
(i 1 দ্বারা বাড়ান)
-
-
-
-
রিটার্ন রিটার্ন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
n :=s
এর আকার -
যদি n 1 এর সমান হয়, তাহলে −
-
ফাঁকা স্ট্রিং ফেরত দিন
-
-
একটি অ্যারে সংজ্ঞায়িত করুন v =lps(গুলি)
-
x :=v[n − 1]
-
ret :=ফাঁকা স্ট্রিং
-
আরম্ভ করার জন্য i :=0, যখন i
-
ret :=ret + s[i]
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
};
main(){
Solution ob;
cout << (ob.longestPrefix("helloworldhello"));
} ইনপুট
"helloworldhello"
আউটপুট
hello
