ধরুন আমাদের স্ট্রিং হিসাবে s আছে, আমাদের অভিধানিক ক্রমে s এর শেষ সাবস্ট্রিংটি খুঁজে বের করতে হবে।
সুতরাং, ইনপুট যদি "abbbcabbc" এর মত হয়, তাহলে আউটপুট হবে "cabbc"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
i :=0,j :=1,k :=0
-
যখন j + k
-
যদি s[i + k] s[j + k] এর মত হয়, তাহলে −
-
(k 1 দ্বারা বাড়ান)
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
যদি s[i + k]
-
i :=j
-
(j 1 দ্বারা বাড়ান)
-
-
অন্যথায়
-
j :=j + k + 1
-
-
k :=0
-
সূচী i থেকে শেষ পর্যন্ত s এর সাবস্ট্রিং ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string lastSubstring(string s) {
int i = 0;
int j = 1;
int k = 0;
while(j + k < s.size()){
if(s[i + k] == s[j + k]) {
k++;
continue;
}
if(s[i + k] < s[j + k]){
i = j;
j++;
}else{
j = j + k + 1;
}
k = 0;
}
return s.substr(i, s.size() - i);
}
};
main(){
Solution ob;
cout << (ob.lastSubstring("abbbcabbc"));
} ইনপুট
"abbbcabbc"
আউটপুট
cabbc
