Hiểu bài toán

Bài toán yêu cầu tính tổng độ dài của tiền tố chung dài nhất (LCP - Longest Common Prefix) giữa chuỗi gốc S và mọi hậu tố của nó. Ví dụ, với S = 'ababaa', các hậu tố là 'ababaa', 'babaa', 'abaa', 'baa', 'aa', 'a'. Ta cần tính: LCP('ababaa', 'ababaa') + LCP('ababaa', 'babaa') + ... và in ra tổng đó.

Các cách tiếp cận

Cách Brute Force

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        long long ans = 0;
        int n = s.length();
        // Duyệt qua tất cả các hậu tố
        for (int i = 0; i < n; i++) {
            int match_len = 0;
            // So sánh hậu tố bắt đầu tại i với chuỗi gốc
            while (match_len + i < n && s[match_len] == s[i + match_len]) {
                match_len++;
            }
            ans += match_len;
        }
        cout << ans << endl;
    }
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Phương pháp này sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài duyệt qua từng vị trí bắt đầu của hậu tố (từ 0 đến n-1). Vòng lặp trong so sánh ký tự của hậu tố hiện tại với ký tự tương ứng của chuỗi gốc để đếm độ dài khớp. Nếu chuỗi toàn ký tự giống nhau (ví dụ 'aaaaa'), độ phức tạp sẽ trở thành O(n^2).

Cách Z-Algorithm

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

vector<int> computeZ(const string &s) {
    int n = s.size();
    vector<int> Z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r)
            Z[i] = min(r - i + 1, Z[i - l]);
        while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]])
            Z[i]++;
        if (i + Z[i] - 1 > r) {
            l = i;
            r = i + Z[i] - 1;
        }
    }
    return Z;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        auto Z = computeZ(s);
        long long res = s.size(); // Trường hợp i=0 (so sánh S với chính nó)
        for (int z : Z) res += z;
        cout << res << '\n';
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Z-Algorithm xây dựng mảng Z, trong đó Z[i] là độ dài tiền tố chung dài nhất giữa chuỗi S và hậu tố bắt đầu tại i.

1. Khởi tạo Z[0] = 0 (hoặc không dùng).
2. Duyệt i từ 1 đến n-1, sử dụng hai con trỏ [L, R] để lưu đoạn khớp dài nhất tìm được.
3. Nếu i nằm trong [L, R], ta có thể tận dụng giá trị Z[i-L] để gán cho Z[i] (trường hợp Z[i-L] < R-i+1).
4. Nếu không, hoặc nếu cần mở rộng, ta tiếp tục so sánh trực tiếp.
5. Kết quả là tổng độ dài các hậu tố khớp với S là tổng các giá trị Z[i] cộng với n (trường hợp hậu tố rỗng/đầu tiên).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm độ dài tiền tố chung (LCP) giữa chuỗi gốc và mọi hậu tố của nó.
• Mảng Z (Z-array) trong Z-Algorithm được định nghĩa chính xác là độ dài tiền tố chung giữa chuỗi S và hậu tố bắt đầu tại chỉ số i, phù hợp hoàn hảo với yêu cầu bài toán.
• Độ phức tạp O(n) của Z-Algorithm là tối ưu cho bài toán này.

Lỗi thường gặp

• Quên cộng độ dài của chính chuỗi S (trường hợp hậu tố bắt đầu tại index 0) vào kết quả cuối cùng.
• Lỗi truy cập ngoài mảng trong khi cài đặt Z-Algorithm nếu không kiểm tra kỹ điều kiện biên của vòng lặp while.
• Sử dụng thuật toán O(n^2) cho các test case lớn dẫn đến Time Limit Exceeded (TLE).