Giả sử chúng ta có s là chuỗi, chúng ta phải tìm chuỗi con cuối cùng của s theo thứ tự từ vựng.
Vì vậy, nếu đầu vào là "abbbcabbc", thì đầu ra sẽ là "cabbc"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
i:=0, j:=1, k:=0
-
while j + k
-
nếu s [i + k] giống với s [j + k] thì -
-
(tăng k lên 1)
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
nếu s [i + k]
-
i:=j
-
(tăng j lên 1)
-
-
Nếu không
-
j:=j + k + 1
-
-
k:=0
-
trả về chuỗi con của s từ chỉ mục i đến cuối
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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"));
} Đầu vào
"abbbcabbc"
Đầu ra
cabbc