นับจำนวนซับสตริงที่มีตัวอักษร X อย่างน้อยหนึ่งครั้งใน C++

เราได้รับสตริง str[] และตัวอักษร X เป้าหมายคือหาซับสตริงของ str[] ที่ทุกซับสตริงมี X อย่างน้อยหนึ่งครั้ง สำหรับ str[]="abc" และ X='a' ซับสตริงที่มี 'a' อย่างน้อยหนึ่งครั้งคือ "a", "ab", "abc" จำนวนคือ 3

มาดูตัวอย่าง

อินพุต − str[] = "aabccd" X='c'

เอาต์พุต − จำนวนซับสตริงที่มีตัวอักษร X อย่างน้อยหนึ่งครั้ง คือ 14

คำอธิบาย − ซับสตริงที่มี 'c' อย่างน้อยหนึ่งตัวจะเป็น: "c", "c", "bc", "cc", "cd", "abc", "bcc", "ccd", "aabc", "abcc", "bccd", "aabcc", "abccd", "aabccd"

อินพุต − str[] = "settings" X='s'

เอาต์พุต − จำนวนซับสตริงที่มีตัวอักษร X อย่างน้อยหนึ่งครั้ง คือ 14

คำอธิบาย − ซับสตริงที่มี 's' อย่างน้อยหนึ่งตัว: "s", "s", "se", "gs", "set", "ngs", "sett", "ings", "setti", "tings", "settin", "ttings", "setting", "ettings", "settings"

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

ในแนวทางนี้เรารู้ว่าจำนวนซับสตริงทั้งหมดของสตริงที่มี n ตัวอักษรคือ n*(n+1)/2

เราจะเดินทางผ่านสตริงและนับตัวอักษรก่อนตัวอักษร X เป็น temp ทันทีที่เจอ X สตริงที่มี X จะมีความยาว temp+1 ตอนนี้เรามี X จำนวนซับสตริงที่มี X จะเป็นตัวอักษรที่เหลือ (length-current index) * (temp+1) บวกเข้า count อัปเดต temp=0 และดำเนินต่อสำหรับ X ถัดไปจนจบสตริง ท้ายสุดเราจะได้ count เป็นจำนวนซับสตริงที่มีตัวอักษร X อย่างน้อยหนึ่งครั้ง

• รับสตริง str และตัวอักษร x
• ฟังก์ชัน sub_x(string str, int length, char x) รับสตริง ความยาว ตัวอักษร x คืนจำนวนซับสตริงที่มีตัวอักษร x อย่างน้อยหนึ่งครั้ง
• กำหนด count เริ่มต้น 0 temp เป็นตัวอักษรก่อน x แรกเป็น 0
• ลูป FOR จาก i=0 ถึง i<length
• ถ้า str[i] == x ความยาวรวม x คือ temp+1 ตัวอักษรเหลือ length-i
• ซับสตริงทั้งหมด (temp+1) * (length-i) บวกเข้า count ตั้ง temp=0 สำหรับรอบต่อไป
• ทำจนจบสตริง
• คืน count

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

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

เอาต์พุต

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

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