Convert Substrings of Length k from Base b to Decimal: แปลง Substring ความยาว k จากฐาน b เป็นฐานสิบใน C++

ปัญหา

กำหนดสตริงตัวเลข str ความยาว k และฐาน b หา Substrings ความยาว k ทุกตัว แปลงจากฐาน b เป็นฐานสิบ (Decimal)

ตัวอย่าง: str="12212", k=3, b=3

• "122"₃ = 1×9 + 2×3 + 2 = 17
• "221"₃ = 2×9 + 2×3 + 1 = 25
• "212"₃ = 2×9 + 1×3 + 2 = 23

อัลกอริทึม

1. วน i = 0 ถึง str.length() - k
2. Extract Substring str.substr(i, k)
3. แปลง Base-b → Decimal: sum = Σ digit[j] × b^(k-1-j)
4. พิมพ์ผลลัพธ์

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

void convertSubstrings(string str, int k, int b) {
    for (int i = 0; i + k <= str.size(); i++) {
        string sub = str.substr(i, k);
        int sum = 0;
        int power = 1;
        
        // คำนวณจากหลักหน่วย (Right to Left)
        for (int j = sub.size() - 1; j >= 0; j--) {
            int digit = sub[j] - '0';
            sum += digit * power;
            power *= b;
        }
        cout << sum << " ";
    }
}

int main() {
    string str = "12212";
    int b = 3, k = 3;
    convertSubstrings(str, k, b);  // 17 25 23
    return 0;
}

การคำนวณตัวอย่าง

Optimization: Sliding Window (O(n))

แทนที่จะคำนวณใหม่ทุกครั้ง ใช้ Rolling Hash:

// val_new = (val_old - first_digit * b^(k-1)) * b + new_digit
// ต้อง precompute b^(k-1)

ความซับซ้อน

• Time: O(n × k) แบบง่าย, O(n) แบบ Sliding Window
• Space: O(1) เพิ่มเติม

Input / Output

Input:  str="12212", k=3, b=3
Output: 17 25 23