C++で文字列を復号化してk番目の文字を求めるプログラムの作成方法

はじめに

このチュートリアルでは、C++を使って「文字列を復号化した後にk番目の文字を見つける」プログラムについて詳しく解説します。

この問題では、英字と数字が混在した文字列と整数Kが与えられます。文字列中の数字は、それまでに読み取った部分の繰り返し回数を表しています。私たちのタスクは、与えられた文字列を復号化し、復号後の文字列におけるK番目の位置にある文字を特定することです。

アプローチ

復号化後の文字列は元の文字列よりも桁違いに長くなる可能性があるため、実際に文字列をメモリ上に展開してしまうのは非効率です。そこで本記事では、復号後の「長さ」だけを追跡することで、省メモリかつ高速に答えを導く手法を紹介します。

1. 文字列を先頭から順に走査します。
2. 英字に到達したら、現在の復号後の長さ（total_len）を1増やします。total_lenがKと一致した時点で、その文字が答えとなります。
3. 数字に到達したら、連続する数字を読み取って数値nを求めます。このとき、復号後の全体の長さは total_len × n 倍になります。
4. Kが total_len × n 以内であれば、答えはすでに読み込み済みの範囲内に存在します。Kを total_len で割った余りから対応する位置を算出し、再帰的に処理することで答えを得ます。
5. Kがまだ範囲外であれば、total_len を更新して走査を続けます。

実装例

ここでは、文字列「ab2c3」と K = 5 のケースを扱います。この文字列は復号化すると「ababcababcababc」となり、5番目の文字は「c」です。

#include <cstdlib>
#include <iostream>
using namespace std;

// 復号化後のk番目の文字を求める関数
char findKthChar(string s, int k) {
    int len = s.length();
    int i = 0;
    int total_len = 0;
    while (i < len) {
        if (isalpha(s[i])) {
            total_len++;
            if (total_len == k)
                return s[i];
            i++;
        }
        else {
            int n = 0;
            while (i < len && !isalpha(s[i])) {
                n = n * 10 + (s[i] - '0');
                i++;
            }
            int next_total_len = total_len * n;
            if (k <= next_total_len) {
                int pos = k % total_len;
                if (!pos) {
                    pos = total_len;
                }
                return findKthChar(s, pos);
            }
            else {
                total_len = next_total_len;
            }
        }
    }
    return -1;
}

int main() {
    string s = "ab2c3";
    int k = 5;
    cout << findKthChar(s, k);
    return 0;
}

出力

c

コードの解説

findKthChar関数では、isalpha関数を使って英字と数字を判定しながら文字列を走査します。英字の間は単純にカウントを進め、数字が出現した時点で復号後の総長を一気に拡大させます。K番目の文字がすでに読み込んだ範囲に含まれる場合は、剰余演算（%）によって対応する元の位置を割り出し、再帰呼び出しで最終的な文字を確定させます。

この手法を用いれば、復号化後の文字列がどれほど長くなっても、元の文字列を一度走査するだけで目的の文字を取得できます。そのため、時間計算量・空間計算量の両面で非常に効率的な実装となっており、競技プログラミングなどでも応用範囲の広いテクニックです。