Đếm số substring chứa ký tự X ít nhất một lần trong C++

Cho chuỗi str[] và ký tự X. Tìm số substring chứa X ít nhất một lần. Ví dụ: "abc", X='a' → "a", "ab", "abc", count = 3.

Ví dụ

Đầu vào − str[] = "aabccd", X = 'c'

Đầu ra − 14

Giải thích − 14 substring chứa ít nhất một 'c'.

Đầu vào − str[] = "settings", X = 's'

Đầu ra − 14

Phương pháp giải

Tổng substring của chuỗi độ dài n là n*(n+1)/2. Duyệt chuỗi, đếm số ký tự trước mỗi X là temp. Khi gặp X, độ dài đoạn chứa X là temp+1. Số ký tự còn lại là length-i. Số substring chứa X này là (temp+1) * (length-i). Cộng vào count, reset temp=0.

• Hàm sub_x(string str, int length, char x).
• Khởi tạo count = 0, temp = 0.
• Duyệt i = 0..length-1:
  • Nếu str[i] == x: count += (temp+1) * (length-i); temp = 0;
  • Ngược lại: temp++.
• Trả về count.

Ví dụ code

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

Đầu ra

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