C++での文字列変換のインプレースアルゴリズム：サイクルリーダー法によるO(n)実装

与えられた文字列に対して、偶数番目の要素をすべて文字列の末尾へ移動する問題を考えます。ただし、要素を移動する際には、偶数番目・奇数番目それぞれのグループ内での相対的な順序を維持しなければなりません。

例えば、入力文字列が「a1b2c3d4e5f6g7h8i9j1k2l3m4」である場合、「abcdefghijklm1234567891234」へ、追加メモリを使わないインプレース処理かつ O(n) の時間計算量で変換します。

アルゴリズムの手順

• サイズが 3^k + 1 の形となる最大の接頭辞部分文字列を切り出します。このステップでは、3^k + 1 が n（文字列の長さ）以下となる最大の非負整数 k を求めます。

• サイクルリーダー反復アルゴリズム（後述）を、インデックス 1, 3, 9, … から開始してこの部分文字列に適用します。サイクルリーダーアルゴリズムにより、この部分文字列内の全要素が正しい位置へ移動されます。つまり、英字は部分文字列の左半分へ、数字は右半分へ移動されます。

• 残りの部分文字列に対して、手順1と手順2を再帰的に適用します。

• 次に、処理済みの部分文字列同士を連結します。どちらか一方の端（例えば左端）から開始し、2つの部分文字列を選んで以下の操作を行います。

  • 最初の部分文字列の後半を反転します。

  • 2番目の部分文字列の前半を反転します。

  • 最初の部分文字列の後半と2番目の部分文字列の前半をまとめて反転します。

• すべての部分文字列が連結されるまで手順4を繰り返します。これは、最初の部分文字列と2番目を連結し、その結果にさらに3番目を連結していく k-way マージと同じ考え方です。

上記のアルゴリズムに基づくC++のコードは以下の通りです。

// 上記アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;

// 文字を入れ替えるユーティリティ関数
void swap(char* a1, char* b1) {
    char t = *a1; *a1 = *b1; *b1 = t;
}

// 文字列 str1[low1..high1] を反転するユーティリティ関数
void reverse(char* str1, int low1, int high1) {
    while (low1 < high1) {
        swap(&str1[low1], &str1[high1]);
        ++low1; --high1;
    }
}

// 偶数番目の要素をすべて末尾へ移すサイクルリーダーアルゴリズム
void cycleLeader(char* str1, int shift1, int len1) {
    int j;
    char item1;
    for (int i = 1; i < len1; i *= 3) {
        j = i;
        item1 = str1[j + shift1];
        do {
            // 奇数インデックスの場合
            if (j & 1)
                j = len1 / 2 + j / 2;
            // 偶数インデックスの場合
            else
                j /= 2;
            // 新しい位置の要素を退避しながら交換
            swap(&str1[j + shift1], &item1);
        } while (j != i);
    }
}

// 文字列を変換するメイン関数。
// 内部で cycleLeader() を利用する
void moveNumberToSecondHalf(char* str1) {
    int k, lenFirst1;
    int lenRemaining1 = strlen(str1);
    int shift1 = 0;

    while (lenRemaining1) {
        k = 0;

        // ステップ1: 3^k + 1 の形となる最大の接頭辞部分配列を求める
        while (pow(3, k) + 1 <= lenRemaining1)
            k++;
        lenFirst1 = pow(3, k - 1) + 1;
        lenRemaining1 -= lenFirst1;

        // ステップ2: 最大の部分配列に対してサイクルリーダーアルゴリズムを実行
        cycleLeader(str1, shift1, lenFirst1);

        // ステップ4.1: 最初の部分配列の後半を反転
        reverse(str1, shift1 / 2, shift1 - 1);

        // ステップ4.2: 2番目の部分文字列の前半を反転
        reverse(str1, shift1, shift1 + lenFirst1 / 2 - 1);

        // ステップ4.3: 最初の部分文字列の後半と2番目の部分文字列の前半をまとめて反転
        reverse(str1, shift1 / 2, shift1 + lenFirst1 / 2 - 1);

        // 最初の部分配列の長さを更新
        shift1 += lenFirst1;
    }
}

// 上記関数を検証するドライバプログラム
int main() {
    char str1[] = "a1b2c3d4e5f6g7";
    moveNumberToSecondHalf(str1);
    cout << str1;
    return 0;
}

出力

abcdefg1234567

計算量について

このアルゴリズムは、各要素がサイクルリーダーの反復によってちょうど1回ずつ移動され、連結時の反転操作も線形時間で完了するため、全体の時間計算量は O(n) となります。また、入力文字列自体を直接書き換えるだけで追加の作業領域をほとんど必要としないため、空間計算量は O(1)（インプレース）です。補助配列を使わずに英字と数字を分離したい場合に有効な手法といえます。