Chuyển đổi tất cả các chuỗi con độ dài 'k' từ cơ số 'b' sang thập phân trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình chuyển đổi tất cả các chuỗi con có độ dài k từ cơ số b sang hệ thập phân.

Mô tả bài toán

Cho một chuỗi ký tự có độ dài nhất định. Nhiệm vụ là trích xuất tất cả các chuỗi con có độ dài k từ chuỗi đã cho và chuyển đổi chúng từ cơ số b sang dạng thập phân.

Ví dụ minh họa

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

// Chuyển đổi các chuỗi con sang thập phân
int convert_substrings(string str, int k, int b) {
    for (int i = 0; i + k <= str.size(); i++) {
        // Lấy chuỗi con
        string sub = str.substr(i, k);
        // Tính giá trị thập phân tương đương
        int sum = 0, counter = 0;
        for (int i = sub.size() - 1; i >= 0; i--) {
            sum = sum + ((sub.at(i) - '0') * pow(b, counter));
            counter++;
        }
        cout << sum << " ";
    }
}

int main() {
    string str = "12212";
    int b = 3, k = 3;
    convert_substrings(str, b, k);
    return 0;
}

Kết quả

17 25 23

Giải thích thuật toán

• Duyệt qua chuỗi gốc để lấy từng chuỗi con độ dài k
• Với mỗi chuỗi con, tính giá trị thập phân bằng cách nhân từng chữ số với lũy thừa của cơ số b
• In ra kết quả của từng chuỗi con

Độ phức tạp: O(n × k) với n là độ dài chuỗi gốc.