C++で辞書式順序の最後の部分文字列を求めるアルゴリズム

文字列 s が与えられたとき、辞書式順序で最も大きい(最後の)部分文字列を求める問題を考えます。

例えば、入力が "abbbcabbc" の場合、出力は "cabbc" となります。

すべての部分文字列を総当たりで比較すると計算量が膨大になりますが、2つのポインタ(i と j)と比較位置を示す変数 k を使うことで、線形時間 O(n) で効率的に解くことができます。

重要な性質

辞書式順序で最大の部分文字列は、必ずある位置から始まり末尾まで続く接尾辞になります。これは、部分文字列を後ろに伸ばしても辞書式順序が小さくなることはないためです。したがって、この問題は「最適な開始位置を見つける問題」として捉えることができます。

アルゴリズムの手順

初期化: i := 0、j := 1、k := 0 とします。i と j は比較対象となる2つの候補開始位置、k は現在比較している文字のオフセットです。

ループ処理: j + k が文字列の長さ未満である間、以下を繰り返します。

• s[i + k] == s[j + k] の場合: 大小がまだ確定しないため、k を1増やして次の文字を比較します。
• s[i + k] < s[j + k] の場合: j から始まる部分文字列の方が大きいため、i := j として開始位置を更新し、j を1進めます。
• それ以外の場合: i 側が大きいため、j := j + k + 1 として、すでに負けが確定した範囲をまとめてスキップします。

各ステップの最後で 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

計算量

各反復で j + k の値が必ず増加するため、全体の計算量は O(n)(n は文字列の長さ)、追加のメモリ使用量は O(1) で抑えられます。接尾辞の比較を効率的にスキップできる点が、このアルゴリズムの大きな強みです。