Khái Niệm Cơ Bản Về Lyndon Word

Một chuỗi ký tự \(S\) được định nghĩa là một từ Lyndon (Lyndon Word) khi và chỉ khi mọi hậu tố của \(S\) đều lớn hơn chính \(S\) theo thứ tự từ điển. Nói cách khác, \(S\) phải là đại diện nhỏ nhất trong tất cả các vòng xoay của nó.

Bài Toán Phân Rã

Nhiệm vụ phân rã Lyndon yêu cầu tách một chuỗi gốc thành dãy các từ Lyndon \(W_1, W_2, \dots, W_k\) sao cho \(S = W_1 + W_2 + \dots + W_k\). Điều kiện bắt buộc ở đây là thứ tự các phần tử phải không tăng dần, tức là \(W_1 \ge W_2 \ge \dots \ge W_k\). Theo lý thuyết, mỗi chuỗi hữu hạn đều tồn tại duy nhất một cách phân rã thỏa mãn quy tắc này.

Các Tính Chất Quan Trọng

• Tính đóng: Nếu \(U\) và \(V\) là hai từ Lyndon mà \(U < V\), thì chuỗi ghép nối \(UV\) vẫn là một từ Lyndon.
• Duy nhất: Không có hai cách phân rã khác nhau cho cùng một chuỗi đầu vào.
• Quan hệ với tiền tố: Giả sử \(Sc\) là tiền tố của một từ Lyndon, với \(|c|=1\). Khi đó, nếu ta thay thế \(c\) bằng bất kỳ ký tự nào lớn hơn nó (\(d > c\)), thì \(Sd\) cũng sẽ trở thành từ Lyndon.
• Không chứa Border: Một từ Lyndon không thể có border (tiền tố trùng với hậu tố).

Thuật Toán Duval Để Xây Dựng Phân Rã

Để thực hiện việc tách chuỗi, ta sử dụng phương pháp vét cạn thông minh dựa trên tính tuần hoàn của các đoạn chưa xử lý. Ý tưởng chính là duy trì con trỏ duyệt và so sánh ký tự hiện tại với ký tự tương ứng trong chu kỳ gần nhất.

Quy trình hoạt động như sau:

1. Vừa xác định khoảng chu kỳ đang xét, vừa quét tới cuối chuỗi.
2. Nếu ký tự mới lớn hơn kỳ vọng, ta xác định kết thúc một từ Lyndon và cập nhật vị trí bắt đầu mới.
3. Nếu ký tự mới bằng ký tự so sánh, ta tiếp tục mở rộng độ dài chu kỳ.
4. Tránh dùng chỉ số cố định, nên thiết kế vòng lặp để nhảy qua các phần đã xác nhận xong.

void tinh_phan_rax(char* input, int length) {
    // Chỉ số bắt đầu của phân đoạn chưa xử lý
    int pos_start = 0;
    while (pos_start < length) {
        // p: vị trí trong chu kỳ hiện tại
        // q: con trỏ đang quét
        int p = pos_start, q = pos_start + 1;
        
        while (q < length && input[q] >= input[p]) {
            if (input[q] == input[p]) {
                p++;
            } else {
                p = pos_start;
            }
            q++;
        }
        
        // Đẩy các từ Lyndon đã tìm thấy vào kết quả
        int len_factor = q - p;
        while (pos_start <= p) {
            xuat_lo_pho_nhap(pos_start, pos_start + len_factor);
            pos_start += len_factor;
        }
    }
}

Ứng Dụng: Tìm Biểu Diễn Nhỏ Nhất

Một ứng dụng phổ biến của phân rã Lyndon là giải quyết bài toán tìm biểu diễn vòng tròn nhỏ nhất (Minimal String Rotation). Chiến lược là nối chuỗi \(S\) với chính nó tạo thành \(SS\), sau đó tiến hành phân rã Lyndon trên \(SS\).

Vị trí bắt đầu của từ Lyndon đầu tiên xuất hiện nằm trong nửa đầu của \(SS\) chính là chỉ số cần tìm. Việc loại bỏ các trường hợp trùng lặp đảm bảo ta luôn thu được kết quả tối ưu về mặt từ điển.

int tim_min_cyclic_shift(const string& str) {
    int n = str.size();
    // Tạo chuỗi kép ảo để tránh tốn bộ nhớ thêm
    // Hoặc tạo chuỗi nhân đôi thực tế
    string doubled = str + str;
    int best_idx = 0;
    int len = doubled.size();
    
    for (int i = 0; i < n; ) {
        best_idx = i;
        int ptr_match = i;
        int ptr_scan = i + 1;
        
        while (ptr_scan < len && doubled[ptr_scan] >= doubled[ptr_match]) {
            if (doubled[ptr_scan] == doubled[ptr_match]) {
                ptr_match++;
            } else {
                ptr_match = i;
            }
            ptr_scan++;
        }
        
        int step = ptr_scan - ptr_match;
        // Bỏ qua toàn bộ các khối giống nhau vừa tìm được
        while (i <= ptr_match) {
            i += step;
        }
    }
    
    return best_idx;
}