Thuật toán tại chỗ (in-place) biến đổi chuỗi trong C++

Cho một chuỗi, chuyển tất cả phần tử ở vị trí chẵn (even-positioned) về cuối chuỗi. Giữ nguyên thứ tự tương đối của các phần tử vị trí chẵn và lẻ.

Ví dụ: "a1b2c3d4e5f6g7h8i9j1k2l3m4" → "abcdefghijklm1234567891234" tại chỗ (in-place) và O(n).

Các bước

• Cắt tiền tố con dài nhất dạng 3^k + 1. Tìm k lớn nhất sao cho 3^k+1 ≤ n.
• Áp dụng thuật toán cycle leader iteration (giải thích dưới) bắt đầu từ chỉ số 1, 3, 9... cho chuỗi con này. Thuật toán đặt tất cả phần tử đến vị trí đúng: chữ cái nửa trái, chữ số nửa phải.
• Xử lý đệ quy phần còn lại (bước 1 và 2).
• Ghép các chuỗi con đã xử lý: từ trái, lấy hai chuỗi con, làm:
  • Đảo nửa sau chuỗi con đầu.
  • Đảo nửa trước chuỗi con thứ hai.
  • Đảo cả nửa sau chuỗi đầu + nửa trước chuỗi hai cùng lúc.
• Lặp bước 4 cho đến khi ghép xong tất cả (giống trộn k-way).

Mã nguồn C++

// In-place string transformation
#include <bits/stdc++.h>
using namespace std;

void swap(char* a1, char* b1) {
    char t = *a1; *a1 = *b1; *b1 = t;
}

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)       // chỉ số lẻ
                j = len1 / 2 + j / 2;
            else             // chỉ số chẵn
                j /= 2;
            swap(&str1[j + shift1], &item1);
        } while (j != i);
    }
}

void moveNumberToSecondHalf(char* str1) {
    int k, lenFirst1;
    int lenRemaining1 = strlen(str1);
    int shift1 = 0;
    while (lenRemaining1) {
        k = 0;
        while (pow(3, k) + 1 <= lenRemaining1) k++;
        lenFirst1 = pow(3, k - 1) + 1;
        lenRemaining1 -= lenFirst1;
        cycleLeader(str1, shift1, lenFirst1);
        reverse(str1, shift1/2, shift1 - 1);
        reverse(str1, shift1, shift1 + lenFirst1/2 - 1);
        reverse(str1, shift1/2, shift1 + lenFirst1/2 - 1);
        shift1 += lenFirst1;
    }
}

int main() {
    char str1[] = "a1b2c3d4e5f6g7";
    moveNumberToSecondHalf(str1);
    cout << str1;
    return 0;
}

Kết quả

abcdefg1234567