Computer >> Máy Tính >  >> Lập trình >> C ++

Đếm chuỗi con chứa ký tự X ít nhất một lần trong C ++

Chúng ta được cung cấp một chuỗi str [] và một ký tự X. Mục đích là tìm các chuỗi con của str [] sao cho tất cả các chuỗi con chứa X ít nhất một lần. Đối với str [] =”abc '' và X =’ a ’, các chuỗi con chứa‘ a ’ít nhất một lần là“ a ”,“ ab ”,“ abc ”. Số lượng là 3.

Hãy cho chúng tôi hiểu với các ví dụ.

Đầu vào - str [] =“aabccd” X =’c’

Đầu ra - Số chuỗi con có chứa ký tự X ít nhất một lần là - 14

Giải thích - Các chuỗi con chứa ít nhất một chữ 'c' sẽ là:“c”, “c”, “bc”, “cc”, “cd”, “abc”, “bcc”, “ccd”, “aabc”, “ abcc ”,“ bccd ”,“ aabcc ”,“ abccd ”,“ aabccd ”.

Đầu vào - str [] =“cài đặt” X =’s’

Đầu ra - Số chuỗi con có chứa ký tự X ít nhất một lần là - 14

Giải thích - Các chuỗi con chứa ít nhất một 's' sẽ là:“s”, “s”, “se”, “gs”, “set”, “ngs”, “setting”, “ings”, “setti”, “ tings ”,“ settin ”,“ ttings ”,“ setting ”,“ ettings ”,“ settings ”

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Theo cách tiếp cận này, chúng ta biết rằng tổng số chuỗi con của chuỗi có n ký tự là n * (n + 1) / 2.

Bây giờ chúng ta sẽ duyệt qua chuỗi và đếm các ký tự trước ký tự X dưới dạng tạm thời. Ngay sau khi gặp X, các chuỗi chứa X sẽ có độ dài temp + 1. Bây giờ chúng ta có X số chuỗi con chứa X sẽ là các ký tự còn lại (chỉ số độ dài-hiện tại) X (temp + 1). Thêm cái này để đếm. Bây giờ cập nhật temp =0 và tiếp tục cho X tiếp theo cho đến cuối chuỗi. Cuối cùng, chúng tôi đếm là số chuỗi con có chứa ký tự X ít nhất một lần.

  • Lấy một chuỗi str và một ký tự x.

  • Hàm sub_x (char str [], int length, char x) nhận một chuỗi, đó là độ dài, ký tự x và trả về số lượng các chuỗi con chứa ký tự x ít nhất một lần.

  • Lấy số lượng ban đầu là 0. Lấy tạm thời là các ký tự trước x đầu tiên trong str [] là 0 ban đầu.

  • Lấy kích thước đếm ban đầu * (size + 1) / 2 cho số tất cả các chuỗi con có thể có của str [].

  • Traverse str [] bằng cách sử dụng vòng lặp for từ i =0 đến i

  • Nếu str [i] không phải là x thì tốc độ tăng dần là các ký tự trước x đầu tiên.

  • Nếu str [i] ==x thì độ dài của chuỗi bao gồm x sẽ là temp + 1. Các ký tự còn lại của str [] sẽ là length-i.

  • Tất cả các chuỗi con sẽ là (temp + 1) * (length-i). Thêm cái này để đếm. Bây giờ hãy cập nhật temp =0 cho lần lặp tiếp theo.

  • Làm điều này cho đến khi đạt đến cuối str [].

  • Kết quả trả về là kết quả cuối cùng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
   int count = 0;
   int temp = 0;
   for (int i = 0; i < length; i++){
      if (str[i] == x){
         int temp_2 = temp + 1;
         count = count + temp_2 * (length - i);
         temp = 0;
      }
      else{
         temp++;
      }
   }
   return count;
}
int main(){
   string str = "abcabbc";
   int length = str.length();
   char x = 'a';
   cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of sub-strings that contain character X at least once are: 19