C++로 사전순 기준 마지막 부분 문자열 찾기

문자열 s가 주어졌을 때, 사전순(lexicographic order)으로 가장 뒤에 오는 부분 문자열을 찾는 문제입니다.

예를 들어 입력 문자열이 "abbbcabbc"라면, 정답은 "cabbc"가 됩니다.

접근 방법

이 문제는 두 개의 포인터를 활용한 비교 기법으로 선형 시간(O(n)) 안에 해결할 수 있습니다. 알고리즘에서는 세 개의 변수를 사용합니다.

• i: 현재까지 발견된 최적 후보의 시작 인덱스
• j: 새로 비교할 후보의 시작 인덱스
• k: 두 후보 구간이 일치하는 길이

알고리즘 단계

1. i = 0, j = 1, k = 0으로 초기화합니다.
2. j + k가 문자열 길이보다 작은 동안 다음 과정을 반복합니다.
   • s[i + k]와 s[j + k]가 같다면 k를 1 증가시키고 다음 반복으로 넘어갑니다.
   • s[i + k] < s[j + k]라면 i를 j로 갱신하고 j를 1 증가시킵니다. 즉, 더 나은 후보를 발견한 경우입니다.
   • 그 외의 경우(j 쪽이 더 작다면) j를 j + k + 1로 이동시킵니다. j부터 j + k까지의 위치는 후보가 될 수 없기 때문입니다.
3. 비교가 끝날 때마다 k를 0으로 초기화합니다.

반복이 종료되면 인덱스 i부터 문자열 끝까지의 부분 문자열이 곧 정답입니다.

C++ 구현 예제

#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