Ở đây chúng ta sẽ thấy một vấn đề khác, trong đó một chuỗi và một giá trị số nguyên khác nói rằng k được cho trước. Chúng ta phải tìm số chuỗi con có độ dài k, có tổng các giá trị ASCII của các ký tự chia hết cho k.
Giả sử một chuỗi là "GABC". Và giá trị của k là 3. Ở đây chuỗi BCG có ASCII tổng 300, ABC có ASCII tổng 294, cả hai đều chia hết cho k =3.
Cách tiếp cận rất đơn giản. Đầu tiên, chúng ta phải tìm giá trị ASCII của các ký tự của chuỗi con đầu tiên, có độ dài là k. Chúng ta phải sử dụng kỹ thuật cửa sổ trượt và trừ ASCII của ký tự đầu tiên của cửa sổ, và thêm ASCII của ký tự tiếp theo sẽ xuất hiện sau khi trượt cửa sổ, chúng ta sẽ tăng số lượng ở mỗi bước, khi tổng chia hết cho k .
Ví dụ
#include <iostream>
using namespace std;
int countKLenSubstr(string str, int k) {
int len = str.length();
int sum = 0;
int count = 0 ;
for (int i = 0; i <len; i++)
sum += str[i] ; //ASCII sum of first substring
if (sum % k == 0)
count++;
for (int i = k; i < len; i++) {
int prev_ascii = str[i-k]; //ASCII of the first character of the window
sum -= prev_ascii;
sum += str[i];
if (sum % k == 0)
count += 1;
}
return count ;
}
int main() {
string s = "BCGABC" ;
int k = 3 ;
cout<<"Number of substrings: " << countKLenSubstr(s, k);
} Đầu ra
Number of substrings: 2