【C++】復号化した文字列からk番目の文字を取得する方法

問題の概要

エンコードされた文字列を考えてみましょう。この形式では、部分文字列の繰り返しが「部分文字列 + 繰り返し回数」で表現されます。たとえば、ab2cd2 という文字列は ababcdcd を意味します。ここで k = 4 が与えられた場合、復号化後の文字列の4番目の文字、つまり b を返すことになります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

1. まず空の復号化用文字列を用意します。
2. 元の文字列を先頭から読み込み、英小文字が続く限り部分文字列として抽出します。
3. 続いて数字が続く限り読み取り、繰り返し回数として記録します(複数桁の数値にも対応)。
4. 抽出した部分文字列を、記録した回数だけ復号化用文字列に連結します。
5. 元の文字列が尽きるまで上記の処理を繰り返し、最後に復号化された文字列のk番目の文字を返します。

C++での実装例

以下に、実際のC++コードを示します。

#include<iostream>
using namespace std;
char findKthCharacter(string str,int k) {
    string decrypted = "";
    string temp;
    int occurrence = 0;
    for (int i=0; str[i]!='\0'; ){
        temp = "";
        occurrence = 0;
        // 英小文字を読み取り、部分文字列を作成
        while (str[i]>='a' && str[i]<='z'){
            temp += str[i];
            i++;
        }
        // 数字を読み取り、繰り返し回数を算出
        while (str[i]>='1' && str[i]<='9') {
            occurrence = occurrence*10 + str[i] - '0';
            i++;
        }
        // 部分文字列を指定回数だけ連結
        for (int j=1; j<=occurrence; j++)
            decrypted = decrypted + temp;
    }
    // 回数指定のない末尾の部分文字列に対応
    if (occurrence==0)
        decrypted = decrypted + temp;
    return decrypted[k-1];
}
int main() {
    string str = "ab4c12ed3";
    int k = 21;
    cout << k << "th character in decrypted string: " << findKthCharacter(str, k);
}

実行結果

入力文字列 ab4c12ed3 は、復号化すると ababababccccccccccccededed になります。21番目の文字を求めると、以下の出力が得られます。

21th character in decrypted string: e

コードのポイント

• 複数桁の回数に対応: c12 のように2桁以上の繰り返し回数も、occurrence*10 + 数字 の計算で正しく処理できます。
• 回数指定なしの部分文字列: ループ終了後に occurrence == 0 の場合、末尾の部分文字列をそのまま連結することで、abc のようなエンコードされていない文字列にも対応しています。

なお、この実装は復号化後の文字列全体を構築するため、計算量は O(N)(Nは復号化後の文字列長)となります。kが非常に大きい場合は、各ブロックの累積文字数を記録しておき、k番目の文字が属するブロックだけを特定する方式にすれば、メモリ使用量を大幅に抑えられます。