นับ Subsequence ความยาว 3 ในสตริงที่กำหนดใน C++

เราได้รับสตริง str และ substring sub_str ความยาว 3 เป้าหมายคือหาจำนวน subsequence ที่ตรงกับ sub_str ใน str

เช่น "act" ปรากฏ 3 ครั้งใน "cataract" (cataract, cataract, cataract)

ตัวอย่าง

อินพุต: str = "settlement", sub_str = "set"

เอาต์พุต: 5

คำอธิบาย: 5 subsequences ที่สะกดได้ "set"

อินพุต: str = "knowledge", sub_str = "now"

เอาต์พุต: 1

แนวทางการแก้ปัญหา (Naive O(n³))

วนลูป 3 ชั้น: หาตัวแรก → หาตัวที่สองหลังตัวแรก → หาตัวที่สามหลังตัวที่สอง

การนำไปใช้ (Implementation)

#include <iostream>
using namespace std;

int subset_occurrence(string str, int length, string sub_str) {
    int count = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == sub_str[0]) {
            for (int j = i + 1; j < length; j++) {
                if (str[j] == sub_str[1]) {
                    for (int k = j + 1; k < length; k++) {
                        if (str[k] == sub_str[2]) count++;
                    }
                }
            }
        }
    }
    return count;
}

int main() {
    string str = "TUTpoinTUTpoinTUT";
    int length = str.length();
    string sub_str = "TUT";
    cout << "Count of subsequence of length three in a given string are: " << subset_occurrence(str, length, sub_str);
    return 0;
}

เอาต์พุต

Count of subsequence of length three in a given string are: 19

หมายเหตุ: สามารถปรับปรุงเป็น O(n) ได้โดยใช้ DP นับจำนวน subsequence "s", "se", "set" สะสมทีละตัวอักษร