Lời giải: Chu kỳ nhỏ nhất bằng KMP

Phân tích

Có một công thức kinh điển: chu kỳ nhỏ nhất d = n - π[n-1]. Nếu n % d == 0 thì d là chu kỳ, ngược lại chu kỳ là n.

Tại sao? Nếu π[n-1] = k, tức là S[0..k-1] vừa là tiền tố vừa là hậu tố của S. Khi đó n = k + (n - k) = k + d, với d = n - k là độ dài "phần thừa" ở giữa. Nếu S có chu kỳ d, thì S lặp n/d lần cùng một xâu con độ dài d, và k chính là n - d.

Độ phức tạp

• Thời gian: O(N)
• Không gian: O(N)

Code mẫu C++

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

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

    // Tinh mang pi
    vector<int> pi(n, 0);
    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;
    }

    // Chu ky nho nhat: d = n - pi[n-1]
    int d = n - pi[n - 1];
    if (n % d == 0) {
        cout << d << endl;   // Co chu ky d
    } else {
        cout << n << endl;   // Khong co chu ky < n
    }
    return 0;
}

Giải thích

• Công thức d = n - π[n-1] xuất phát từ việc S được hình thành bằng cách nối phần "core block" d lặp lại.
• Ví dụ S = "abcabcabc", n = 9, π[8] = 6, d = 3. Vì 9 % 3 == 0 nên chu kỳ = 3.
• Nếu n = 7 và S = "abcabca" (không lặp hoàn chỉnh), S không có chu kỳ < 7.