ค้นหาจำนวนสตริงย่อยที่มีความยาว k ซึ่งผลรวมของค่า ASCII ของอักขระหารด้วย k ใน C ++ ลงตัว

ที่นี่เราจะเห็นปัญหาอื่น โดยที่สตริงหนึ่งและค่าจำนวนเต็มอีกตัวหนึ่งระบุว่า k ถูกกำหนด เราต้องหาจำนวนสตริงย่อยที่มีความยาว k ซึ่งผลรวมของค่า ASCII ของอักขระหารด้วย k ลงตัว

สมมติว่าสตริงคือ “BCGABC” และค่าของ k คือ 3 ในที่นี้สตริง BCG มีผลรวม ASCII 300, ABC มีผลรวม ASCII 294 ทั้งคู่หารด้วย k =3 ลงตัว

วิธีการนั้นง่าย ขั้นแรกเราต้องหาค่า ASCII ของอักขระของสตริงย่อยแรกที่มีความยาว k เราต้องใช้เทคนิคหน้าต่างบานเลื่อนและลบ 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