Chuỗi con cuối cùng theo thứ tự từ điển trong C++

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ừ điển.

Vì vậy, nếu đầu vào giống như "abbbcabbc", thì đầu ra sẽ là "cabbc"

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −

• i := 0, j := 1, k := 0

• khi j + k < kích thước của s, thực hiện &minsu;

  • nếu s[i + k] bằng s[j + k], thì −

    • (tăng k lên 1)

    • Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo

  • nếu s[i + k] < s[j + k], thì −

    • i := j

    • (tăng j lên 1)

  • Ngược lại

    • j := j + k + 1

  • k := 0

trả về chuỗi con của s từ chỉ số i đến cuối

Hãy xem 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