สมมติว่าเรามี s เป็นสตริง เราต้องหาสตริงย่อยสุดท้ายของ s ตามลำดับศัพท์
ดังนั้น หากอินพุตเป็นเหมือน "abbbcabbc" ผลลัพธ์จะเป็น "cabbc"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ผม :=0,j :=1,k :=0
-
ขณะที่ j + k <ขนาดของ s ทำ &minsu;
-
ถ้า s[i + k] เหมือนกับ s[j + k] แล้ว −
-
(เพิ่ม k ขึ้น 1)
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
ถ้า s[i + k]
-
ผม :=เจ
-
(เพิ่มขึ้น j โดย 1)
-
-
มิฉะนั้น
-
j :=j + k + 1
-
-
k :=0
-
ส่งคืนสตริงย่อยของ s จากดัชนี i ไปยังจุดสิ้นสุด
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
