Đếm chuỗi con bắt đầu bằng ký tự X và kết thúc bằng ký tự Y trong C++

Cho chuỗi str. Đếm chuỗi con bắt đầu bằng ký tự X và kết thúc bằng ký tự Y. Ví dụ "artact", X='a', Y='t' → "art", "act", "artact" (3 chuỗi con).

Ví dụ

Đầu vào: str = "abcccdef", X = 'a', Y = 'c'
Đầu ra: 3 ("abc", "abcc", "abccc").

Đầu vào: str = "tempest", X = 't', Y = 't'
Đầu ra: 3 ("t", "tempest", "t").

Giải thuật

Duyệt chuỗi, đếm số lần xuất hiện của X (x_total). Khi gặp Y, cộng x_total vào kết quả (mỗi X trước đó có thể cặp với Y này tạo thành chuỗi con).

Ví dụ triển khai

#include <bits/stdc++.h>
using namespace std;

int X_Y(string str, int length, char X, char Y) {
    int count = 0, x_total = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == X) x_total++;
        if (str[i] == Y) count += x_total;
    }
    return count;
}

int main() {
    string str = "defaabbcchhkl";
    int length = str.size();
    char X = 'd', Y = 'a';
    cout << "Count of substrings that starts with character X and ends with character Y are: " << X_Y(str, length, X, Y);
    return 0;
}

Kết quả

Count of substrings that starts with character X and ends with character Y are: 2