Phân tích Lyndon (thuật toán Duval)
Từ Lyndon, định lý Chen-Fox-Lyndon và thuật toán Duval phân tích xâu trong O(n) thời gian, O(1) bộ nhớ; ứng dụng tìm xoay vòng nhỏ nhất, hậu tố nhỏ nhất của mọi tiền tố và đếm vòng cổ.
Từ Lyndon (Lyndon word) là xâu khác rỗng nhỏ hơn mọi hậu tố thật sự của nó theo thứ tự từ điển, ví dụ a, ab, aab, abb, aabab. Định lý Chen-Fox-Lyndon nói rằng mọi xâu viết được duy nhất dưới dạng với mỗi là từ Lyndon và . Thuật toán Duval tìm phân tích này trong thời gian và chỉ bộ nhớ phụ (ba con trỏ), thay vì thử mọi cách cắt hay so sánh hậu tố trong . Hệ quả quan trọng nhất trong thi đấu: tìm xoay vòng nhỏ nhất theo từ điển (minimal cyclic rotation) của xâu độ dài trong , cùng với hậu tố nhỏ nhất của mọi tiền tố và các bài đếm vòng cổ.
Ý tưởng / Trực giác
Từ Lyndon
Xâu là từ Lyndon khi với mọi hậu tố thật sự của . Một định nghĩa tương đương: nhỏ hơn ngặt mọi phép xoay khác của nó. Suy ra ngay:
- Ký tự đầu của từ Lyndon là ký tự nhỏ nhất của nó, và từ Lyndon không có biên (border): không có tiền tố thật sự nào đồng thời là hậu tố.
- Từ Lyndon là nguyên thủy (primitive), không viết được dạng với :
ababkhông phải Lyndon vì hậu tốablà tiền tố của nó nênab < abab.
Ví dụ: aab là Lyndon (các hậu tố ab, b đều lớn hơn aab); aba không phải (hậu tố a < aba); ba không phải (hậu tố a < ba).
Hai bổ đề dùng xuyên suốt:
- Ghép: nếu là từ Lyndon và thì là từ Lyndon.
- Mở rộng: nếu là từ Lyndon, là tiền tố thật sự của (có thể rỗng), là ký tự đứng sau trong và , thì là từ Lyndon với mọi .
Phân tích Chen-Fox-Lyndon
Tồn tại: bắt đầu với mỗi ký tự là một nhân tử (một ký tự luôn là từ Lyndon). Hễ còn hai nhân tử kề nhau thì gộp chúng (bổ đề ghép). Số nhân tử giảm dần nên quá trình dừng, và khi dừng thì dãy không tăng.
Duy nhất: phải là tiền tố Lyndon dài nhất của . Thật vậy, giả sử có phân tích mà ngắn hơn tiền tố Lyndon dài nhất ; kết thúc ở giữa một nhân tử nào đó, tức với là tiền tố khác rỗng của . Khi đó (vì Lyndon, là hậu tố thật sự), mà và là tiền tố của , nên : mâu thuẫn. Cắt ra rồi lặp lại cho phần còn lại.
Một tính chất rất hay dùng: nhân tử cuối chính là hậu tố nhỏ nhất của .
Thuật toán Duval: bất biến
Duval đọc xâu từ trái sang phải với ba con trỏ . Phần đã được xuất thành các nhân tử cuối cùng. Phần đang xét luôn có dạng
và , tức là ký tự của "thẳng hàng" với vị trí nếu chu kỳ được nối dài. Xét ký tự mới :
| So sánh | Ý nghĩa | Cập nhật |
|---|---|---|
| nối tiếp chu kỳ, dài thêm (đủ thì tăng) | , | |
| Theo bổ đề mở rộng, cả trở thành một từ Lyndon mới | , | |
| (hoặc hết xâu) | Không thể nối dài được nữa: bản sao của là nhân tử cuối cùng | xuất lần, đặt về đầu , làm lại |
Vì sao trường hợp cuối được phép "chốt" ? Mọi xâu bắt đầu tại và chứa đều có dạng với , nên nhỏ hơn hậu tố của chính nó: không thể là từ Lyndon. Vậy tiền tố Lyndon dài nhất bắt đầu tại chính là , và lặp lại lý luận cho bản sao. Phần chưa chắc chốt được, nên ta đọc lại nó từ đầu.
Độ dài chu kỳ luôn là , nên khi chốt, mỗi nhân tử có độ dài . Đó là toàn bộ thuật toán.
Ví dụ chạy tay
Phân tích abaabaaab (, chỉ số từ ):
array base=0 a b a a b a a a b step Vòng 1: i = 0, xét s[0..2] = aba pointer i 0 pointer k 1 pointer j 3 highlight blue 0..2 step s[k] = b > s[j] = a: chốt nhân tử ab, đặt i = 2 highlight green 0..1 pointer i 2 pointer k - pointer j - step Vòng 2: i = 2, đọc tới s[2..6] = aabaa, dừng ở j = 7 pointer i 2 pointer k 4 pointer j 7 highlight blue 2..6 step s[k] = b > s[j] = a: chốt nhân tử aab, đặt i = 5 highlight orange 2..4 pointer i 5 pointer k - pointer j - step Vòng 3: i = 5, đọc tới hết xâu, chốt aaab highlight purple 5..8
Chi tiết từng bước ( là chu kỳ hiện tại, độ dài sau cập nhật):
| Vòng | vs | Cập nhật | Dạng | |||
|---|---|---|---|---|---|---|
| 1 | 0 | a < b |
ab |
ab |
||
| 2 | 0 | a = a |
aba |
ab + a |
||
| 3 | 1 | b > a |
dừng | xuất ab (), |
||
| 3 | 2 | a = a |
aa |
a, |
||
| 4 | 3 | a < b |
aab |
aab |
||
| 5 | 2 | a = a |
aaba |
aab + a |
||
| 6 | 3 | a = a |
aabaa |
aab + aa |
||
| 7 | 4 | b > a |
dừng | xuất aab (), |
||
| 6 | 5 | a = a |
aa |
a |
||
| 7 | 6 | a = a |
aaa |
a, |
||
| 8 | 7 | a < b |
aaab |
aaab |
||
| 9 | 5 | hết xâu | dừng | xuất aaab (), |
Kết quả ab | aab | aaab, đúng là dãy không tăng: ab > aab > aaab. Nhân tử cuối aaab cũng là hậu tố nhỏ nhất của . Chú ý ở vòng 2, phần aa (vị trí ) đã được đọc nhưng không thuộc nhân tử aab, nên vòng 3 đọc lại nó.
Xoay vòng nhỏ nhất
Mọi phép xoay của là một đoạn con độ dài của . Chạy Duval trên ; đầu xoay vòng nhỏ nhất là vị trí bắt đầu của nhân tử cuối cùng có điểm đầu .
Phác thảo lý do: một phép xoay bắt đầu ở giữa một nhân tử thua phép xoay bắt đầu ở đầu , vì nhỏ hơn mọi hậu tố thật sự của nó, và độ dài nhân tử không vượt quá ( có chu kỳ nên một đoạn dài hơn luôn có biên, không thể là từ Lyndon). Giữa các điểm đầu nhân tử, nhân tử sau không lớn hơn nhân tử trước, nên điểm đầu càng về sau càng tốt, miễn là còn .
Với abaabaaab, abaabaaab abaabaaab phân tích thành
ab | aab | aaababaab | aaab
0 2 5 14
Các nhân tử bắt đầu tại ; điểm đầu cuối cùng là , nên xoay vòng nhỏ nhất là aaab + abaab = aaababaab. Vì chỉ cần điểm đầu, cài đặt không lưu nhân tử mà chỉ ghi lại ở đầu mỗi vòng ngoài, và dừng khi .
So sánh với các cách khác
| Cách | Thời gian | Bộ nhớ phụ | Ghi chú |
|---|---|---|---|
| Thử mọi phép xoay | Chỉ dùng để kiểm tra | ||
| Suffix array trên | Nặng, nhưng cho luôn thứ tự của mọi phép xoay | ||
| Hashing + tìm nhị phân LCP | Dễ code, có xác suất sai | ||
| Thuật toán Booth | Biến thể hàm tiền tố KMP trên , khó nhớ | ||
| Biểu diễn nhỏ nhất (hai con trỏ) | Rất ngắn, xem bên dưới | ||
| Duval trên | nếu truy cập | Cùng một vòng lặp với phân tích Lyndon |
Biểu diễn nhỏ nhất (minimal expression) giữ hai ứng viên và độ dài khớp . So với : bằng thì tăng; nếu ký tự của lớn hơn thì mọi điểm đầu đều bị loại (mỗi điểm thua ), nên , tương tự với . Mỗi bước loại ít nhất một ứng viên hoặc tăng , tổng :
// Smallest index of the minimal rotation, two pointers, O(n) time, O(1) memory
int min_expression(const string& s) {
int n = s.size(), i = 0, j = 1, k = 0;
while (i < n && j < n && k < n) {
char a = s[(i + k) % n], b = s[(j + k) % n];
if (a == b) { k++; continue; }
if (a > b) i += k + 1; else j += k + 1;
if (i == j) j++;
k = 0;
}
return min(i, j);
}
Cài đặt
Chương trình đọc xâu , in phân tích Lyndon (các nhân tử cách nhau một dấu cách), rồi in chỉ số nhỏ nhất của xoay vòng nhỏ nhất cùng với chính xâu xoay đó. Với đầu vào abaabaaab, cả hai phiên bản in:
ab aab aaab
5 aaababaab
#include <bits/stdc++.h>
using namespace std;
// Lyndon factorization (Duval): returns the factors s = w1 w2 ... wm, w1 >= w2 >= ... >= wm.
// O(n) time, O(1) extra memory besides the output.
vector<string> duval(const string& s) {
int n = s.size();
vector<string> factors;
int i = 0;
while (i < n) {
// s[i..j-1] is always of the form w w ... w w' (w Lyndon, w' a proper prefix of w),
// k = j - |w| is the position to compare with s[j].
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j]) k = i; // s[i..j] becomes a single Lyndon word
else k++; // s[j] continues the period |w| = j - k
j++;
}
// s[k] > s[j] (or end of string): output every full copy of w
while (i <= k) {
factors.push_back(s.substr(i, j - k));
i += j - k;
}
}
return factors;
}
// Smallest index of the lexicographically minimal rotation, Duval on s + s.
int min_rotation(const string& s) {
int n = s.size();
string t = s + s;
int i = 0, ans = 0;
while (i < n) {
ans = i; // the factor starting at i is a candidate
int j = i + 1, k = i;
while (j < 2 * n && t[k] <= t[j]) {
if (t[k] < t[j]) k = i;
else k++;
j++;
}
while (i <= k) i += j - k;
}
return ans;
}
int main() {
string s;
cin >> s;
vector<string> f = duval(s);
for (size_t x = 0; x < f.size(); x++) cout << f[x] << (x + 1 < f.size() ? ' ' : '\n');
int r = min_rotation(s);
cout << r << ' ' << s.substr(r) + s.substr(0, r) << '\n';
}
import sys
def duval(s):
"""Lyndon factorization: s = w1 w2 ... wm with w1 >= w2 >= ... >= wm."""
n = len(s)
factors = []
i = 0
while i < n:
# s[i:j] = w w ... w w', k = j - len(w)
j, k = i + 1, i
while j < n and s[k] <= s[j]:
if s[k] < s[j]:
k = i # s[i..j] becomes a single Lyndon word
else:
k += 1 # continues the period
j += 1
while i <= k: # output every full copy of w
factors.append(s[i:i + j - k])
i += j - k
return factors
def min_rotation(s):
"""Smallest index of the lexicographically minimal rotation (Duval on s + s)."""
n = len(s)
t = s + s
i = ans = 0
while i < n:
ans = i
j, k = i + 1, i
while j < 2 * n and t[k] <= t[j]:
k = i if t[k] < t[j] else k + 1
j += 1
while i <= k:
i += j - k
return ans
def main():
s = sys.stdin.readline().strip()
print(*duval(s))
r = min_rotation(s)
print(r, s[r:] + s[:r])
main()
Hậu tố nhỏ nhất và phân tích Lyndon của mọi tiền tố
Gọi là điểm đầu của hậu tố nhỏ nhất của tiền tố , cũng là điểm đầu nhân tử Lyndon cuối cùng của tiền tố đó. Mảng này tính được trong cùng vòng lặp Duval:
- Khi : cả là một từ Lyndon, nên .
- Khi : và cấu trúc của nó giống hệt cấu trúc lùi một chu kỳ, nên .
- Các vị trí bị đọc lại sau khi chốt nhân tử được tính lại, giá trị cũ bị ghi đè.
Từ , phân tích Lyndon của tiền tố là phân tích của nối thêm nhân tử , nên đi ngược theo chuỗi là liệt kê được. Chương trình in mảng rồi in phân tích của từng tiền tố (phần in này tốn chỉ để minh hoạ, bản thân mảng là ). Với abaabaaab:
0 0 2 3 2 5 6 7 5
a: a
ab: ab
aba: ab a
abaa: ab a a
abaab: ab aab
abaaba: ab aab a
abaabaa: ab aab a a
abaabaaa: ab aab a a a
abaabaaab: ab aab aaab
#include <bits/stdc++.h>
using namespace std;
// last[j] = start of the minimal suffix of s[0..j]
// = start of the last Lyndon factor of the prefix s[0..j].
// Same loop as Duval, O(n) total.
vector<int> min_suffix_of_prefixes(const string& s) {
int n = s.size();
vector<int> last(n);
int i = 0;
while (i < n) {
int j = i + 1, k = i;
last[i] = i; // a single character is a Lyndon word
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j]) {
k = i;
last[j] = i; // s[i..j] is one Lyndon word
} else {
last[j] = last[k] + (j - k); // repeat the structure one period back
k++;
}
j++;
}
while (i <= k) i += j - k; // positions >= new i are recomputed
}
return last;
}
int main() {
string s;
cin >> s;
int n = s.size();
vector<int> last = min_suffix_of_prefixes(s);
for (int j = 0; j < n; j++) cout << last[j] << (j + 1 < n ? ' ' : '\n');
// Factorization of the prefix s[0..j]: follow last[] backwards
for (int j = 0; j < n; j++) {
vector<string> f;
for (int e = j; e >= 0; e = last[e] - 1) f.push_back(s.substr(last[e], e - last[e] + 1));
reverse(f.begin(), f.end());
cout << s.substr(0, j + 1) << ':';
for (auto& w : f) cout << ' ' << w;
cout << '\n';
}
}
import sys
def min_suffix_of_prefixes(s):
"""last[j] = start of the minimal suffix (= last Lyndon factor) of s[0..j]."""
n = len(s)
last = [0] * n
i = 0
while i < n:
j, k = i + 1, i
last[i] = i
while j < n and s[k] <= s[j]:
if s[k] < s[j]:
k = i
last[j] = i
else:
last[j] = last[k] + (j - k)
k += 1
j += 1
while i <= k:
i += j - k
return last
def main():
s = sys.stdin.readline().strip()
last = min_suffix_of_prefixes(s)
print(*last)
for j in range(len(s)):
f = []
e = j
while e >= 0:
f.append(s[last[e]:e + 1])
e = last[e] - 1
print(s[:j + 1] + ":", *reversed(f))
main()
Mọi chương trình trên (C++ và Python), cùng với hàm biểu diễn nhỏ nhất, đã được so khớp với lời giải trâu (tìm tiền tố Lyndon dài nhất bằng định nghĩa, thử mọi phép xoay, thử mọi hậu tố) trên xâu ngẫu nhiên độ dài với bảng chữ cái a, ab, az, abc; bản C++ chạy dưới giây với .
Độ phức tạp
- Thời gian . Ở mỗi vòng ngoài, vòng trong đọc ký tự (), sau đó tiến . Vì nên : số ký tự đọc trong một vòng nhỏ hơn hai lần số ký tự được chốt. Tổng số bước vòng trong vì thế nhỏ hơn , và mỗi bước là . Với xoay vòng nhỏ nhất, xâu có độ dài nên tổng nhỏ hơn .
- Bộ nhớ phụ. Chỉ ba số nguyên (không tính mảng kết quả). Khi tìm xoay vòng nhỏ nhất, có thể không tạo mà truy cập để giữ . Bản tính cần thêm mảng .
⚠️ Lỗi thường gặp
- Viết nhầm điều kiện vòng trong thành
s[k] < s[j]. Trường hợp bằng nhau là nơi chu kỳ được nối dài; thiếu nó,aabbị cắt thànha | ab(sai vìa < ab, dãy không còn không tăng). Điều kiện đúng làs[k] <= s[j], bên trong phân biệt<(đặtk = i) và=(tăngk). - Xuất cả phần khi chốt. Chỉ xuất các bản sao đầy đủ của : vòng
while (i <= k) i += j - k;dừng đúng khi tới đầu . Xuất tới sẽ cho nhân tử không phải Lyndon (ở ví dụ trên sẽ raaabaa). - Tìm xoay vòng nhỏ nhất bằng Duval trên thay vì . Nhân tử cuối của là hậu tố nhỏ nhất, không phải xoay vòng nhỏ nhất: với
ba, hậu tố nhỏ nhất làanhưng xoay vòng nhỏ nhất làab, còn vớiabaabaaabhai vị trí này trùng nhau (cùng là ) chỉ là tình cờ. Luôn nối và chỉ lấy điểm đầu . - Lấy điểm đầu không phải nhỏ nhất khi xâu tuần hoàn. Với
abab, cả vị trí và đều choabab. Cài đặt ở trên ghians = iở đầu vòng ngoài với và trả về chỉ số nhỏ nhất (). Nếu đề hỏi "số bước xoay ít nhất" thì đây là đáp án đúng; nếu sửa vòng lặp (ví dụ dừng theo ), hãy kiểm tra lại vớiaaaavàabab. - So sánh
charcó dấu. Với byte (UTF-8) hoặc dãy số được nén thànhchar,charcó dấu làm thứ tự sai. Dùngunsigned charhoặcvector<int>. - Nhầm "nhân tử không tăng" với "không giảm". Định lý Chen-Fox-Lyndon yêu cầu ; các nhân tử bằng nhau là hợp lệ (
aaa=a | a | a). Nếu tự viết hàm kiểm tra, đừng đòi giảm ngặt. - Thứ tự hậu tố "tiền tố nhỏ hơn". Mọi lý luận ở đây dùng thứ tự từ điển chuẩn, trong đó tiền tố thật sự nhỏ hơn xâu dài hơn (
a < ab). Nếu đề định nghĩa so sánh khác (ví dụ thêm ký tự lính canh lớn ở cuối), kết quả hậu tố nhỏ nhất có thể khác.
Biến thể / Mở rộng
- Kiểm tra hai xâu là xoay vòng của nhau: đưa mỗi xâu về dạng chuẩn là xoay vòng nhỏ nhất của nó, hai xâu tương đương khi và chỉ khi dạng chuẩn bằng nhau. Dùng để nhóm các xâu theo lớp xoay, hoặc làm khoá cho hash map. Cách khác là tìm trong bằng Z-function hoặc KMP.
Đếm từ Lyndon và vòng cổ. Số từ Lyndon độ dài trên bảng chữ cái ký tự là
với là hàm Möbius. Mỗi vòng cổ (lớp xoay) độ dài tương ứng đúng một từ Lyndon độ dài (xoay vòng nhỏ nhất của nó là ), nên số vòng cổ là , khớp với kết quả của bổ đề Burnside. Ví dụ : với , còn .
- Sinh mọi từ Lyndon độ dài theo thứ tự từ điển (thuật toán Fredricksen-Kessler-Maiorana, Duval 1988): từ từ hiện tại , lặp cho đủ độ dài , bỏ các ký tự lớn nhất ở cuối rồi tăng ký tự cuối lên một. Ghép các từ Lyndon có độ dài chia hết theo thứ tự sinh ra cho dãy de Bruijn nhỏ nhất theo từ điển.
- Hậu tố nhỏ nhất của mọi tiền tố (mảng ở trên) giúp trả lời "xâu con nhỏ nhất theo từ điển bắt đầu trong đoạn" hoặc làm bước con trong các bài tham lam trên xâu. Muốn so sánh hậu tố tổng quát hơn thì dùng suffix array hoặc suffix automaton.
- Lyndon trong lý thuyết xâu nâng cao. Từ Lyndon là công cụ chính trong chứng minh và thuật toán tìm mọi "runs" (đoạn lặp cực đại) trong của Bannai và cộng sự (mỗi run có một "gốc Lyndon" theo một trong hai thứ tự bảng chữ cái), và trong biến đổi Burrows-Wheeler song ánh (bijective BWT).
Bài tập luyện
- Xoay xâu bằng nhau (rotequal) (Trung bình): các xâu ngắn nên thử trâu là đủ, nhưng điều kiện "có đáp án" chính là mọi xâu có cùng dạng chuẩn (xoay vòng nhỏ nhất), luyện ý tưởng dạng chuẩn của lớp xoay.
- Xoay Nhỏ Nhất (minrot) (Khó): xoay vòng nhỏ nhất của xâu độ dài , cài thẳng Duval trên .
- Đếm vòng cổ (cntnecklace) (Khó): đếm vòng cổ hạt màu; lời giải chính dùng Burnside, có thể đối chiếu với công thức qua đếm từ Lyndon.
- Xoay vòng nhỏ nhất từ điển (lexrot) (Khó): cùng bài toán với , thử cả ba cách Duval, Booth và biểu diễn nhỏ nhất để so sánh.
Kho bài hiện chưa có bài nào dùng riêng hậu tố nhỏ nhất của mọi tiền tố hay sinh từ Lyndon; phần đó tạm dừng ở mức lý thuyết và code mẫu bên trên.
Bình luận