Hướng dẫn giải của Đếm

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, truongik, asenen_kiet, oqtn75

Hiểu bài toán

Cho một xâu S có độ dài n. Với mỗi i từ 1 đến n, xét xâu con tiền tố S[0...i-1] (gọi là Pi). Nhiệm vụ là tính số lần xuất hiện của Pi trong toàn bộ xâu S (bao gồm cả các lần xuất hiện chồng lấp) và in ra dãy kết quả tương ứng cho từng i. Ví dụ, với S = 'abababa', P1 = 'a' xuất hiện 4 lần, P2 = 'ab' xuất hiện 3 lần, ..., P_7 = 'abababa' xuất hiện 1 lần. N = ~10^2~.

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

Cách Quy hoạch động sử dụng mảng tiền tố (KMP)
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s; cin >> s;
    int n = s.size();
    vector<int> pi(n), cnt(n + 1, 0);

    // 1. Tính mảng tiền tố KMP
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }

    // 2. Đếm số lần mỗi độ dài tiền tố xuất hiện
    // cnt[len] lưu số lượng tiền tố có độ dài len
    for (int i = 0; i < n; i++) {
        cnt[pi[i]]++;
    }

    // 3. Tính toán số lần xuất hiện của các tiền tố
    // Duyệt từ độ dài lớn về nhỏ, cộng dồn số lượng
    // Nếu một tiền tố độ dài L xuất hiện, nó cũng là tiền tố của các độ dài nhỏ hơn
    for (int len = n; len > 0; len--) {
        int parent_len = pi[len - 1];
        if (parent_len > 0) {
            cnt[parent_len] += cnt[len];
        }
    }

    // 4. In kết quả
    // Với mỗi độ dài i, số lần xuất hiện là cnt[i] (các vị trí không phải bắt đầu)
    // +1 cho vị trí bắt đầu (tiền tố chính nó)
    for (int i = 1; i <= n; i++) {
        cout << cnt[i] + 1 << " ";
    }
    return 0;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Tiếp cận này sử dụng thuật toán KMP.

  1. Tính mảng pi (mảng tiền tố). pi[i] là độ dài dài nhất của tiền tố của S[0...i] mà cũng là hậu tố của nó.
  2. Duyệt qua mảng pi, đếm tần suất xuất hiện của các giá trị pi[i]. Ví dụ: nếu pi[i] = 5, có nghĩa là tại vị trí i, có một tiền tố độ dài 5 xuất hiện.
  3. Quy hoạch động từ độ dài lớn xuống nhỏ: Nếu một xâu con P có độ dài L xuất hiện k lần, thì mọi tiền tố của P cũng xuất hiện ít nhất k lần. Do đó, ta cộng dồn số lượng: cnt[pi[L-1]] += cnt[L].
  4. Kết quả cho độ dài i là cnt[i] (số lần xuất hiện tại các vị trí giữa) cộng thêm 1 (lần xuất hiện tại vị trí 0).
Cách Z-Algorithm
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();

    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; 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;
        }
    }

    // cnt[len] = số lần Z[i] >= len
    // Ban đầu đếm chính xác số lần Z[i] = len
    vector<long long> cnt(n + 1, 0);
    for (int i = 1; i < n; i++) {
        if (z[i] > 0)
            cnt[z[i]]++;
    }

    // Cộng dồn từ trên xuống (từ n về 1)
    // Nếu Z[i] >= L, thì nó cũng >= L-1, L-2, ...
    for (int i = n; i >= 1; i--) {
        cnt[i] += cnt[i + 1];
    }

    // In kết quả: cnt[i] là số lần tiền tố độ dài i xuất hiện ở các vị trí sau
    // +1 cho tiền tố tại vị trí 0
    for (int i = 1; i <= n; i++) {
        cout << cnt[i] + 1;
        if (i < n) cout << " ";
    }

    return 0;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Z-Algorithm tính mảng Z, trong đó Z[i] là độ dài tiền tố chung dài nhất của S và S[i...].

  1. Tính mảng Z cho xâu S.
  2. Z[i] = L có nghĩa là tại vị trí i, tiền tố độ dài L xuất hiện. Do đó, ta đếm tần suất của các giá trị Z.
  3. Để biết số lần tiền tố độ dài i xuất hiện, ta cần cộng dồn: tất cả các vị trí có Z[k] >= i.
  4. Ta dùng mảng cnt, cộng dồn từ n về 1: cnt[i] += cnt[i+1].
  5. Kết quả là cnt[i] + 1 (lần xuất hiện tại vị trí 0).
Cách Brute Force (Tính toán trực tiếp)
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    for (int i = 1; i <= n; ++i) {
        string prefix = s.substr(0, i);
        int count = 0;
        // Kiểm tra xem prefix xuất hiện bao nhiêu lần trong s
        for (int j = 0; j <= n - i; ++j) {
            if (s.substr(j, i) == prefix) {
                count++;
            }
        }
        cout << count << (i == n ? "" : " ");
    }
    return 0;
}
  • Time Complexity: O(n^3)
  • Space Complexity: O(1)

Đây là cách giải quyết trực quan nhất. Với mỗi độ dài i từ 1 đến n:

  1. Lấy xâu tiền tố P = S[0...i-1].
  2. Duyệt qua tất cả các vị trí j trong S để kiểm tra xem S[j...j+i-1] có bằng P không.
  3. Đếm và in kết quả.

Cách này hoạt động đúng nhưng rất chậm. Với n=100, nó có thể qua được do n nhỏ, nhưng là một phương pháp tối ưu kém.

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

Cách tiếp cận Time Space Tên
1 O(n) O(n) Quy hoạch động sử dụng mảng tiền tố (KMP)
2 O(n) O(n) Z-Algorithm
3 O(n^3) O(1) Brute Force (Tính toán trực tiếp)

Bài học kinh nghiệm

  • Bài toán yêu cầu đếm số lần xuất hiện của các tiền tố S[0...i] trong toàn bộ xâu S.
  • Thuật toán KMP (mảng pi) và Z-Algorithm là các công cụ mạnh mẽ để xử lý vấn đề về xâu con và tiền tố.
  • Vấn đề có thể biến đổi thành: Với mỗi độ dài L, đếm số lượng chỉ số i sao cho S[0...L-1] là tiền tố của S[i...].

Lỗi thường gặp

  • Quên cộng thêm 1 cho lần xuất hiện của tiền tố tại chính vị trí đầu tiên (vị trí 0).
  • Xử lý sai việc cộng dồn kết quả (ví dụ duyệt từ đầu đến cuối thay vì từ cuối lên đầu trong Z-Algorithm).
  • Lỗi truy cập mảng ngoài biên (ví dụ pi[i-1] khi i=0).

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.