Hiểu bài toán

Cho một dãy số A gồm n phần tử. Dãy B được gọi là ước của dãy A nếu như ghép liên tiếp (lặp lại) một số nguyên lần dãy B thì ta thu được dãy A. Tìm độ dài (số lượng phần tử) của dãy ước ngắn nhất. Ví dụ, với dãy [1, 3, 1, 3, 1, 3], dãy ước là [1, 3] và độ dài là 2.

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

Cách Brute Force (Tìm kiếm tuần tự)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Thử tất cả các độ dài k từ 1 đến n
    for (int k = 1; k <= n; k++) {
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (a[i] != a[i % k]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << k;
            return 0;
        }
    }
    return 0;
}

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

Cách tiếp cận này thử lần lượt các độ dài k từ 1 đến n. Với mỗi k, nó kiểm tra xem dãy A có phải là lặp lại của một đoạn đầu tiên độ dài k hay không. Cụ thể, với chỉ số i, ta so sánh a[i] với a[i % k]. Nếu tất cả đều khớp, k là câu trả lời. Đây là cách đơn giản nhất nhưng chưa tối ưu.

Cách Optimized Brute Force (Tối ưu hóa)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int k = 1; k <= n; k++) {
        // Chỉ kiểm tra các k là ước số của n
        if (n % k != 0) continue;

        bool ok = true;
        for (int i = k; i < n; i++) {
            if (a[i] != a[i % k]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << k;
            return 0;
        }
    }
    return 0;
}

• Time Complexity: O(n * số lượng ước của n)
• Space Complexity: O(n)

Cải tiến từ cách brute force. Nhận thấy rằng nếu dãy A được tạo thành từ dãy ước B có độ dài k, thì độ dài n của A phải chia hết cho k. Do đó, ta chỉ cần kiểm tra các giá trị k mà n chia hết (các ước của n). Bên cạnh đó, vòng lặp kiểm tra chỉ cần chạy từ k đến n-1, vì các phần tử từ 0 đến k-1 là chính chúng (vô điều kiện khớp).

Cách KMP Algorithm (Knuth-Morris-Pratt)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Xây dựng mảng lps (longest proper prefix which is also suffix)
    vector<int> lps(n, 0);
    int len = 0;
    int i = 1;
    while (i < n) {
        if (a[i] == a[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    // Độ dài chu kỳ = n - lps[n-1] (nếu n chia hết cho độ dài này)
    int cycle_len = n - lps[n - 1];
    if (n % cycle_len == 0) {
        cout << cycle_len;
    } else {
        cout << n;
    }

    return 0;
}

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

Sử dụng thuật toán KMP để tìm độ dài của chu kỳ lặp. Mảng lps trong KMP giúp xác định phần tiền tố dài nhất đồng thời là hậu tố. Nếu một dãy có chu kỳ, thì 'chu kỳ' sẽ là phần bù của phần tiền tố/luffix tìm được. Cụ thể, độ dài chu kỳ = n - lps[n-1]. Nếu n chia hết cho độ dài này, đó là câu trả lời, ngược lại chu kỳ là chính dãy A (độ dài n).

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

Bài học kinh nghiệm

• Độ dài của dãy ước (k) phải là một ước số của độ dài dãy A (n).
• Bài toán có thể coi là tìm chu kỳ lặp của một chuỗi.
• Nếu lps[n-1] > 0 và n % (n - lps[n-1]) == 0 thì chu kỳ có độ dài n - lps[n-1].

Lỗi thường gặp

• Quên kiểm tra điều kiện n % k == 0 trong các giải thuật tối ưu, dẫn đến TLE hoặc sai kết quả.
• Sai chỉ số khi so sánh a[i] với a[i % k] (ví dụ so sánh sai với phần tử đầu tiên của chu kỳ).
• Xử lý trường hợp không có chu kỳ lặp (k = n) không chính xác.