นับจำนวนสระในทุกสับสตริงของสตริงที่กำหนดด้วย C++

ได้รับสตริง str ที่มีตัวอักษรภาษาอังกฤษ เป้าหมายคือหาจำนวนสระ (vowels) ที่เกิดขึ้นในทุกสับสตริง (substring) ของ str ถ้าสตริงคือ "abcde" สับสตริงจะเป็น "a", "b", "c", "d", "e", "ab", "bc", "cd", "de", "abc", "bcd", "cde", "abcd", "bcde", "abcde" จำนวนสระในสับสตริงเหล่านี้คือ 10 (a และ e)

ตัวอย่าง

Input

str = "aloe"

Output

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

Explanation

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

Input

str="http"

Output

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

Explanation

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

วิธีการที่ใช้ในโปรแกรม

วิธีนี้สร้างเวกเตอร์ vec ที่เก็บจำนวนครั้งที่ตัวอักษรตัวที่ i ปรากฏในทุกสับสตริงไว้ที่ vec[i]

ตัวอักษรตัวที่ 0 เกิดขึ้นใน n สับสตริง โดย n คือความยาวของสตริง str

ตัวอักษรตัวที่ i เกิดขึ้นในสับสตริงที่มีมันอยู่ (n-i) + จำนวนสับสตริงที่มีตัวที่ i และตัวก่อนหน้า (arr[i-1]) - จำนวนสับสตริงที่เกิดจากตัวก่อนหน้าเพียงอย่างเดียว (i)

• รับสตริง str เป็นอินพุต
• ฟังก์ชัน substring_vowels_count(string str, int length) คืนค่าจำนวนสระในทุกสับสตริง
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• สร้างเวกเตอร์จำนวนเต็ม vec
• วนลูป i=0 ถึง length เติม vec ด้วยจำนวนครั้งที่ตัวอักษรตัวที่ i ปรากฏในทุกสับสตริง
• ถ้า i=0 สำหรับตัวอักษรตัวแรก จำนวนคือ length ตั้ง vec[0]=length
• สำหรับตัวอักษรอื่น ตั้งด้วย push_back(temp_1 + temp_2) โดย temp_1=length-i และ temp_2=vec[i-1]-i
• วนลูป str อีกครั้ง สำหรับแต่ละ str[i] ที่เป็นสระ (a, e, i, o, u) บวก vec[i] เข้า count
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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