Đếm số xâu con khác nhau trong chuỗi trong C++

Cho chuỗi str. Nhiệm vụ: đếm tất cả các xâu con (substring) khác nhau của str. Xâu con là chuỗi liên tiếp nằm trong chuỗi gốc.

Ví dụ 1

Input – str = "wxyz"

Output – 10

Giải thích: wxyz, wxy, wx, w, xyz, xy, x, yz, y, z.

Ví dụ 2

Input – str = "zzzz"

Output – 4

Giải thích: zzzz, zzz, zz, z.

Thuật toán cơ bản (O(N²) thời gian, O(N²) không gian)

1. Duyệt vị trí bắt đầu i = 0..n-1.
2. Duyệt vị trí kết thúc j = i..n-1.
3. Lấy substring str[i..j], insert vào unordered_set.
4. Kết quả = size của set.

Ví dụ code (cơ bản)

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    string str = "aaaa";
    unordered_set<string> myset;
    
    for (int i = 0; i < str.size(); i++) {
        string sub = "";
        for (int j = i; j < str.size(); j++) {
            sub += str[j];
            myset.insert(sub);
        }
    }
    
    cout << "Count of distinct substrings: " << myset.size() << endl;
    return 0;
}

Kết quả

Count of distinct substrings: 4

Lưu ý: Code gốc in `str.size()` thay vì `myset.size()` - đây là bug. Đã sửa trong phiên bản trên.

Tối ưu hóa (O(N) - Suffix Automaton / Suffix Array)

Với N lớn (10^5), cần dùng Suffix Automaton (SAM) hoặc Suffix Array + LCP.

Công thức với Suffix Array: Tổng độ dài suffix - Tổng LCP = n(n+1)/2 - ΣLCP[i].

// Suffix Automaton approach (sketch)
struct State { int len, link; map next; };
// Build SAM, answer = sum(len[v] - len[link[v]]) for all states v

Độ phức tạp SAM: O(N) thời gian, O(N) không gian.