Đếm số nguyên âm xuất hiện trong tất cả các xâu con của chuỗi cho trước trong C++

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

Ví dụ

Đầu vào

str = "aloe"

Đầu ra

Số nguyên âm trong tất cả xâu con của chuỗi cho trước là: 14

Giải thích

Các xâu con là: "a", "l", "o", "e", "al", "lo", "oe", "alo", "loe", "aloe". Tổng nguyên âm trong đây là: 14

Đầu vào

str="http"

Đầu ra

Số nguyên âm trong tất cả xâu con của chuỗi cho trước là: 0

Giải thích

Các xâu con là: "h", "t", "t", "p", "ht", "tt", "tp", "htt", "ttp", "http". Tổng nguyên âm trong đây là: 0

Phương pháp sử dụng

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

Ký tự thứ 0 xuất hiện trong n xâu con, trong đó n là độ dài xâu str.

Ký tự thứ i xuất hiện trong tất cả các xâu con chứa nó (n-i) + số xâu con chứa ký tự thứ i cũng như ký tự trước đó (arr[i-1]) - số xâu con chỉ được hình thành bởi các ký tự trước đó (i).

Nhận xâu str làm đầu vào.
Hàm substring_vowels_count(string str, int length) nhận str với độ dài và trả về số lượng nguyên âm xuất hiện trong tất cả các xâu con của xâu cho trước.
Khởi tạo biến đếm ban đầu là 0.
Tạo vector nguyên vec.
Duyệt vec bằng vòng lặp for từ i=0 đến i<length và điền nó với số lần xuất hiện của ký tự vị trí i trong tất cả xâu con của str.
Nếu i=0, đối với ký tự thứ 0, số lượng này là length. Đặt vec[0]=length bằng push_back(length).
Đối với tất cả các ký tự khác, đặt bằng push_back(temp_1 + temp_2) trong đó temp_1 = length-i và temp_2 = vec[i-1] - i.
Bây giờ duyệt str lại bằng vòng lặp for và với mỗi str[i] là nguyên âm (a, e, i, o, u). Cộng vec[i] vào biến đếm.
Cuối cùng, chúng ta sẽ có tổng số lần xuất hiện của nguyên âm trong các xâu con trong biến đếm.
Trả về biến đếm làm kết quả.

Ví dụ mã

#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 << "Số nguyên âm trong tất cả xâu con của chuỗi cho trước là: " << substring_vowels_count(str, length);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số nguyên âm trong tất cả xâu con của chuỗi cho trước là: 28