Đếm dãy con độ dài 3 trong chuỗi cho trước trong C++

Cho chuỗi str và chuỗi con sub_str độ dài 3. Đếm số lần sub_str xuất hiện như một dãy con (subsequence) trong str. Ví dụ "act" xuất hiện 3 lần trong "cataract".

Ví dụ

Đầu vào: str = "settlement", sub_str = "set"
Đầu ra: 5.

Đầu vào: str = "knowledge", sub_str = "now"
Đầu ra: 1.

Giải thuật

Duyệt 3 vòng lặp lồng nhau: tìm ký tự đầu của sub_str trong str, từ đó tìm ký tự thứ 2, sau đó tìm ký tự thứ 3. Mỗi bộ 3 chỉ số tăng dần tạo ra 1 dãy con.

Ví dụ triển khai

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

Kết quả

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