Cho một chuỗi và một số nguyên k. Cần tìm số lượng chuỗi con độ dài k mà tổng giá trị ASCII của các ký tự chia hết cho k.
Ví dụ: chuỗi "BCGABC", k = 3. Chuỗi con "BCG" có tổng ASCII = 300, "ABC" có tổng = 294, cả hai đều chia hết cho 3.
Cách làm: dùng kỹ thuật cửa sổ trượt (sliding window). Tính tổng ASCII của chuỗi con đầu tiên độ dài k. Sau đó trượt cửa sổ: trừ ASCII của ký tự đầu, cộng ASCII của ký tự mới vào. Tăng đếm mỗi khi tổng chia hết cho k.
Ví dụ mã C++
#include <iostream>
using namespace std;
int demChuoiConK(string str, int k) {
int len = str.length();
int sum = 0;
int count = 0;
for (int i = 0; i < len; i++)
sum += str[i]; // tổng ASCII của chuỗi con đầu tiên
if (sum % k == 0)
count++;
for (int i = k; i < len; i++) {
int prev_ascii = str[i-k]; // ASCII của ký tự đầu cửa sổ
sum -= prev_ascii;
sum += str[i];
if (sum % k == 0)
count += 1;
}
return count;
}
int main() {
string s = "BCGABC";
int k = 3;
cout << "Số lượng chuỗi con: " << demChuoiConK(s, k);
}
Kết quả đầu ra
Số lượng chuỗi con: 2