復号化された文字列のk番目の文字を求める – C++実装（セット2）

概念

エンコードされた文字列では、部分文字列の繰り返しが「部分文字列＋繰り返し回数」の形式で表されます。例えば、暗号化された文字列が「pq2rs2」で k=5 の場合、復号化された文字列は「pqpqrsrs」となり、5番目の文字は「r」であるため、出力は「r」になります。

なお、暗号化された部分文字列の繰り返し回数は2桁以上になることもあります。例えば「pq12r3」では、「pq」が12回繰り返されます。このとき、繰り返し回数の先頭に0が付くことはありません。

入力例

"p2q2r3", k = 6

出力

r

復号化された文字列は「ppqqrrr」です。

入力例

"pq4r2ts3", k = 11

出力

t

復号化された文字列は「pqpqpqpqrrtststs」です。

アルゴリズム（解法手順）

• 現在の部分文字列の長さを求めます。2つのポインタを使用し、1つを部分文字列の先頭に固定し、もう1つを数字が見つかるまで進めます。
• 2つ目のポインタをさらに進め、アルファベットが見つかるまで移動することで、部分文字列の繰り返し回数（頻度）を求めます。
• 頻度に元の部分文字列の長さを掛け合わせて、繰り返し後の部分文字列の長さを求めます。
• この長さが k より小さい場合、目的の文字は次の部分文字列に存在します。k からこの長さを引くことで、まだカバーすべき文字数を管理します。
• この長さが k 以上の場合、目的の文字は現在の部分文字列内に存在します。k は1始まりのインデックスであるため、1を引いた後、元の部分文字列の長さで剰余を取ります。こうして得られた位置、すなわち最初のポインタが指す部分文字列の先頭から k 番目の文字が答えとなります。

実装例（C++）

// 復号化された文字列からK番目の文字を求めるC++プログラム
#include <bits/stdc++.h>
using namespace std;

// エンコードされた文字列からK番目の文字を求める関数
char encodedChar(string str, int k) {
    int a, b;
    int m = str.length();
    int len1;   // 部分文字列の長さを格納
    int num1;   // 繰り返し後の部分文字列の長さを格納
    int freq1;  // 部分文字列の繰り返し回数を格納

    a = 0;
    while (a < m) {
        b = a;
        len1 = 0;
        freq1 = 0;

        // 数字が見つかるまで文字列を走査し、部分文字列の長さを求める
        while (b < m && isalpha(str[b])) {
            b++;
            len1++;
        }

        // 直前の部分文字列の繰り返し回数を求める
        while (b < m && isdigit(str[b])) {
            freq1 = freq1 * 10 + (str[b] - '0');
            b++;
        }

        // 繰り返し後の部分文字列の長さを求める
        num1 = freq1 * len1;

        // 繰り返し後の長さがkより小さい場合、目的の文字は
        // 次の部分文字列に存在する。kから長さを引いて、
        // 残りカバーすべき文字数を管理する
        if (k > num1) {
            k -= num1;
            a = b;
        }
        // 繰り返し後の長さがk以上の場合、
        // 目的の文字は現在の部分文字列内に存在する
        else {
            k--;
            k %= len1;
            return str[a + k];
        }
    }

    // 文字列に繰り返しが含まれない場合の処理
    // 例: str="abced"
    return str[k - 1];
}

// ドライバーコード
int main() {
    string str1 = "pqpqpqpqrrtststs";
    int k1 = 11;
    cout << encodedChar(str1, k1) << endl;

    string str2 = "p2q2r3";
    int k2 = 6;
    cout << encodedChar(str2, k2) << endl;

    return 0;
}

出力

t
r

計算量

このアルゴリズムは、エンコードされた文字列を一度だけ走査するため、時間計算量は O(n)（n はエンコードされた文字列の長さ）です。また、補助的な記憶領域は O(1) で済みます。実際に復号化後の文字列を構築しないため、展開後の文字列が非常に長くなる場合でも、効率的に目的の文字を求められる点が大きな利点です。