นี่คือโจทย์อีกข้อหนึ่ง ที่ให้สตริงหนึ่งและจำนวนเต็ม k เราต้องหาจำนวนซับสตริงความยาว k ที่ผลรวมค่า ASCII ของตัวอักษรหาร k ลงตัว
สมมติสตริงคือ "BCGABC" และ k = 3 ซับสตริง BCG มีผลรวม ASCII 300, ABC มีผลรวม 294 ทั้งคู่หาร 3 ลงตัว
วิธีแก้คือ หาค่า ASCII ของตัวอักษรในซับสตริงแรกที่ยาว k ใช้เทคนิค sliding window ลบ ASCII ของตัวแรกในหน้าต่าง และบวก ASCII ของตัวถัดไปหลังเลื่อนหน้าต่าง เพิ่มนับทุกครั้งที่ผลรวมหาร k ลงตัว
ตัวอย่าง
#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); }ผลลัพธ์
Number of substrings: 2
