Đếm chuỗi con có ký tự đầu và cuối giống nhau trong C++

Cho chuỗi str. Đếm chuỗi con có ký tự bắt đầu và kết thúc giống nhau. Ví dụ "baca" → "b","a","c","a","aca" (5 chuỗi con).

Ví dụ

Đầu vào: str = "abaefgf"
Đầu ra: 9 ("a","b","a","e","f","g","f","aba","fgf").

Đầu vào: str = "abcdef"
Đầu ra: 6 (chỉ 6 ký tự đơn lẻ).

Phương pháp 1: Vét cạn (Naive)

Duyệt mọi chuỗi con, kiểm tra ký tự đầu và cuối.

Phương pháp 2: Hiệu quả (Tần suất)

Kết quả chỉ phụ thuộc vào tần suất của mỗi ký tự. Nếu ký tự 'a' xuất hiện f lần → số chuỗi con bắt đầu và kết thúc bằng 'a' là f * (f + 1) / 2. Tổng over tất cả ký tự.

Ví dụ triển khai (Hiệu quả)

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

int check_Start_End(string str, int length) {
    int count = 0;
    int arr[MAXIMUM] = {0};
    for (int i = 0; i < length; i++) {
        arr[str[i] - 'a']++;
    }
    for (int i = 0; i < MAXIMUM; i++) {
        count += arr[i] * (arr[i] + 1) / 2;
    }
    return count;
}

int main() {
    string str = "bcbdedfef";
    int length = str.length();
    cout << "Count of substrings with same first and last characters are: " << check_Start_End(str, length);
    return 0;
}

Kết quả

Count of substrings with same first and last characters are: 13