C++ Tìm số chuỗi con của một chuỗi

Tìm số chuỗi con (không rỗng) có thể tạo thành từ một chuỗi cho trước.

Input: "moon" → Output: 10
Các chuỗi con: 'm', 'o', 'o', 'n', 'mo', 'oo', 'on', 'moo', 'oon', 'moon'

Input: "yellow" → Output: 21

Phương pháp giải

Cho chuỗi độ dài n. Số chuỗi con = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2.

Ví dụ minh họa

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

int main() {
    string str = "yellow";
    int n = str.length();
    int number_of_strings = n * (n + 1) / 2;
    cout << "Số chuỗi con của chuỗi: " << number_of_strings;
    return 0;
}

Kết quả

Số chuỗi con của chuỗi: 21

Giải thích

Công thức n(n+1)/2 cho số chuỗi con không rỗng. Chỉ cần lấy độ dài chuỗi và áp dụng công thức. Độ phức tạp O(1).

Kết luận

Đã trình bày công thức tính số chuỗi con và code C++. Áp dụng được cho C, Java, Python. Hy vọng hữu ích.