Đếm số nguyên âm xuất hiện trong tất cả các chuỗi con của chuỗi đã cho trong C ++

Cho một chuỗi str chứa các bảng chữ cái tiếng Anh. Mục đích là để tìm số nguyên âm xuất hiện trong tất cả các chuỗi con của str. Nếu chuỗi là “abcde” thì các chuỗi con sẽ là “a”, “b”, “c”, “d”, “e”, “ab”, “bc”, “cd”, “de”, “abc”, “Bcd”, “cde”, “abcd”, “bcde”, “abcde”. Số nguyên âm trong các chuỗi con này là 10. (a và e)

Ví dụ

Đầu vào

str = ”aloe”

Đầu ra

Count the number of vowels occurring in all the substrings of given string are:
14

Giải thích

The substrings are:
“a”, “l”, “o”, “e”, “al”, “lo”, “oe”, “alo”, “loe”, “aloe”. Total vowels in these are: 14

Đầu vào

str=”http”

Đầu ra

Count the number of vowels occurring in all the substrings of given string are:
0

Giải thích

The substrings are:
“h”, “t”, “t”, “p”, “ht”, “tt”, “tp”, “htt”, “ttp”, “http”. Total vowels in these are: 0

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

Trong cách tiếp cận này, chúng ta sẽ tạo một vec vectơ, lưu trữ số lần xuất hiện của ký tự thứ i trong tất cả các chuỗi con trong vec [i].

Ký tự thứ 0 xuất hiện trong n chuỗi con trong đó n là độ dài của chuỗi str.

Ký tự thứ i xuất hiện trong tất cả các chuỗi con chứa nó (n − i) + số chuỗi con chứa ký tự thứ i cũng như ký tự trước đó (arr [i − 1]) - số chuỗi con chỉ được tạo bởi các ký tự trước đó (i).

• Lấy một chuỗi str làm đầu vào.

• Hàm substring_vowels_count (string str, int length) nhận str với độ dài của nó và trả về số lượng các nguyên âm xuất hiện trong tất cả các chuỗi con của một chuỗi đã cho.

• Lấy số lượng ban đầu là 0.

• Lấy một vec-tơ số nguyên.

• Duyệt vec bằng cách sử dụng vòng lặp for từ i-0 đến i

• Nếu i =0, đối với ký tự thứ 0, số lượng này là độ dài. Đặt vec [0] =length usingpush_back [length].

• Đối với tất cả các ký tự khác được đặt bằng cách sử dụng push_back (temp_1 + temp_2) trong đótemp_1 =length − 1 và temp_2 =vec [i − 1] −i.

• Bây giờ duyệt str một lần nữa bằng cách sử dụng vòng lặp for và cho mỗi str [i] là nguyên âm, (a, e, i, o, hoặc u). Thêm vec [i] để đếm.

• Cuối cùng, chúng ta sẽ đếm được tổng số lần xuất hiện của các nguyên âm trong chuỗi con.

• Kết quả là số lượt trả lại.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int substring_vowels_count(string str, int length){
   int count = 0;
   vector<int> vec;
   for (int i = 0; i < length; i++){
      if (i == 0){
         vec.push_back(length);
      } else {
         int temp_1 = length − i;
         int temp_2 = vec[i − 1] − i;
         vec.push_back(temp_1 + temp_2);
      }
   }
   for (int i = 0; i < length; i++){
      if(str[i] == 'a' || str[i] == 'i' || str[i] == 'e' || str[i] == 'o' || str[i] == 'u'){
         count = count + vec[i];
      }
   }
   return count;
}
int main(){
   string str = "honesty";
   int length = str.length();
   cout<<"Count the number of vowels occurring in all the substrings of given string are: "<<substring_vowels_count(str, length);
   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 the number of vowels occurring in all the substrings of given string are: 28