C++ 사전순의 마지막 부분 문자열

s를 문자열로 가지고 있다고 가정하고 사전순으로 s의 마지막 부분 문자열을 찾아야 합니다.

따라서 입력이 "abbbcabbc"와 같으면 출력은 "cabbc"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

• 동안 j + k

  • s[i + k]가 s[j + k]와 같으면 -

    • (k를 1씩 증가)

    • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

  • s[i + k]

    • 나는 :=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