Wiki › Thuật toán › Thuật toán xâu › Phân tích Lyndon (thuật toán Duval)

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ổ.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 21 phút 1 lượt xem

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 s viết được duy nhất dưới dạng s=w1w2⋯wm với mỗi wi là từ Lyndon và w1≥w2≥⋯≥wm. Thuật toán Duval tìm phân tích này trong O(n) thời gian và chỉ O(1) bộ nhớ phụ (ba con trỏ), thay vì thử mọi cách cắt hay so sánh hậu tố trong O(n2). 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 106 trong O(n), 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 w là từ Lyndon khi w<v với mọi hậu tố thật sự v của w. Một định nghĩa tương đương: w 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 uk với k≥2: abab không phải Lyndon vì hậu tố ab là tiền tố của nó nên ab < 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:

  1. Ghép: nếu u,v là từ Lyndon và u<v thì uv là từ Lyndon.
  2. Mở rộng: nếu w là từ Lyndon, w′ là tiền tố thật sự của w (có thể rỗng), b là ký tự đứng sau w′ trong w và c>b, thì wmw′c là từ Lyndon với mọi m≥1.
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 wi<wi+1 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: w1 phải là tiền tố Lyndon dài nhất của s. Thật vậy, giả sử có phân tích mà w1 ngắn hơn tiền tố Lyndon dài nhất u; u kết thúc ở giữa một nhân tử wj nào đó, tức u=w1⋯wj−1v với v là tiền tố khác rỗng của wj. Khi đó u<v (vì u Lyndon, v là hậu tố thật sự), mà v≤wj≤w1 và w1 là tiền tố của u, nên u<w1≤u: mâu thuẫn. Cắt w1 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 wm chính là hậu tố nhỏ nhất của s.

Thuật toán Duval: bất biến

Duval đọc xâu từ trái sang phải với ba con trỏ i≤k<j. Phần s[0..i−1] đã được xuất thành các nhân tử cuối cùng. Phần đang xét s[i..j−1] luôn có dạng

s[i..j−1]=wmw′,w là từ Lyndon, m≥1, w′ là tiền tố thật sự của w,

và k=j−|w|, tức s[k] là ký tự của w "thẳng hàng" với vị trí j nếu chu kỳ |w| được nối dài. Xét ký tự mới s[j]:

So sánh Ý nghĩa Cập nhật
s[j]=s[k] s[j] nối tiếp chu kỳ, w′ dài thêm (đủ |w| thì m tăng) k←k+1, j←j+1
s[j]>s[k] Theo bổ đề mở rộng, cả s[i..j] trở thành một từ Lyndon mới k←i, j←j+1
s[j]<s[k] (hoặc hết xâu) Không thể nối dài được nữa: m bản sao của w là nhân tử cuối cùng xuất w m lần, đặt i về đầu w′, làm lại

Vì sao trường hợp cuối được phép "chốt" w? Mọi xâu bắt đầu tại i và chứa s[j] đều có dạng wmw′c với c<b, nên nhỏ hơn hậu tố w′c 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 i chính là w, và lặp lại lý luận cho m bản sao. Phần w′ chưa chắc chốt được, nên ta đọc lại nó từ đầu.

Độ dài chu kỳ luôn là j−k, nên khi chốt, mỗi nhân tử có độ dài j−k. Đó là toàn bộ thuật toán.

Ví dụ chạy tay

Phân tích s= abaabaaab (n=9, chỉ số từ 0):

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 (w là chu kỳ hiện tại, độ dài j−k sau cập nhật):

Vòng j k s[k] vs s[j] Cập nhật s[i..j] Dạng wmw′
i=0 1 0 a < b k←0 ab w= ab
2 0 a = a k←1 aba ab + a
3 1 b > a dừng xuất ab (j−k=2), i←2
i=2 3 2 a = a k←3 aa w= a, m=2
4 3 a < b k←2 aab w= aab
5 2 a = a k←3 aaba aab + a
6 3 a = a k←4 aabaa aab + aa
7 4 b > a dừng xuất aab (j−k=3), i←5
i=5 6 5 a = a k←6 aa w= a
7 6 a = a k←7 aaa w= a, m=3
8 7 a < b k←5 aaab w= aaab
9 5 hết xâu dừng xuất aaab (j−k=4), i←9

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 s. Chú ý ở vòng 2, phần aa (vị trí 5,6) đã đượ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 s là một đoạn con độ dài n của t=s+s. Chạy Duval trên t; đầ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 <n.

Phác thảo lý do: một phép xoay bắt đầu ở giữa một nhân tử w thua phép xoay bắt đầu ở đầu w, vì w 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á n (t có chu kỳ n nên một đoạn dài hơn 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 <n.

Với s= abaabaaab, t= 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 0,2,5,14; điểm đầu cuối cùng <9 là 5, nên xoay vòng nhỏ nhất là s[5..8]+s[0..4]= 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 i ở đầu mỗi vòng ngoài, và dừng khi i≥n.

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 O(n2) O(n) Chỉ dùng để kiểm tra
Suffix array trên s+s O(nlogn) O(n) Nặng, nhưng cho luôn thứ tự của mọi phép xoay
Hashing + tìm nhị phân LCP O(nlogn) O(n) Dễ code, có xác suất sai
Thuật toán Booth O(n) O(n) Biến thể hàm tiền tố KMP trên s+s, khó nhớ
Biểu diễn nhỏ nhất (hai con trỏ) O(n) O(1) Rất ngắn, xem bên dưới
Duval trên s+s O(n) O(1) nếu truy cập s[pmodn] 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 i≠j và độ dài khớp k. So s[(i+k)modn] với s[(j+k)modn]: bằng thì k tăng; nếu ký tự của i lớn hơn thì mọi điểm đầu i,i+1,…,i+k đều bị loại (mỗi điểm i+p thua j+p), nên i←i+k+1, tương tự với j. Mỗi bước loại ít nhất một ứng viên hoặc tăng k, tổng O(n):

// 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 s, 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
C++
#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';
}
Python
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 last[j] là điểm đầu của hậu tố nhỏ nhất của tiền tố s[0..j], 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 s[j]>s[k]: cả s[i..j] là một từ Lyndon, nên last[j]=i.
  • Khi s[j]=s[k]: s[i..j]=wmw′ và cấu trúc của nó giống hệt cấu trúc lùi một chu kỳ, nên last[j]=last[k]+(j−k).
  • 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ừ last, phân tích Lyndon của tiền tố s[0..j] là phân tích của s[0..last[j]−1] nối thêm nhân tử s[last[j]..j], nên đi ngược theo chuỗi j→last[j]−1 là liệt kê được. Chương trình in mảng last rồi in phân tích của từng tiền tố (phần in này tốn O(n2) chỉ để minh hoạ, bản thân mảng là O(n)). 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
C++
#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';
    }
}
Python
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 1500 xâu ngẫu nhiên độ dài 1..14 với bảng chữ cái a, ab, az, abc; bản C++ chạy dưới 0.2 giây với n=106.

Độ phức tạp

  • Thời gian O(n). Ở mỗi vòng ngoài, vòng trong đọc j−i ký tự (s[i..j−1]=wmw′), sau đó i tiến m|w|. Vì |w′|<|w|≤m|w| nên m|w|>(j−i)/2: 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 2n, và mỗi bước là O(1). Với xoay vòng nhỏ nhất, xâu có độ dài 2n nên tổng nhỏ hơn 4n.
  • Bộ nhớ O(1) phụ. Chỉ ba số nguyên i,j,k (không tính mảng kết quả). Khi tìm xoay vòng nhỏ nhất, có thể không tạo s+s mà truy cập s[pmodn] để giữ O(1). Bản tính last cần thêm mảng O(n).

⚠️ 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ó, aab bị cắt thành a | 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 < (đặt k = i) và = (tăng k).
  • Xuất cả phần w′ khi chốt. Chỉ xuất các bản sao đầy đủ của w: vòng while (i <= k) i += j - k; dừng đúng khi i tới đầu w′. Xuất tới j sẽ cho nhân tử không phải Lyndon (ở ví dụ trên sẽ ra aabaa).
  • Tìm xoay vòng nhỏ nhất bằng Duval trên s thay vì s+s. Nhân tử cuối của s là hậu tố nhỏ nhất, không phải xoay vòng nhỏ nhất: với s= ba, hậu tố nhỏ nhất là a nhưng xoay vòng nhỏ nhất là ab, còn với abaabaaab hai vị trí này trùng nhau (cùng là 5) chỉ là tình cờ. Luôn nối s+s và chỉ lấy điểm đầu <n.
  • Lấy điểm đầu không phải nhỏ nhất khi xâu tuần hoàn. Với s= abab, cả vị trí 0 và 2 đều cho abab. Cài đặt ở trên ghi ans = i ở đầu vòng ngoài với i<n và trả về chỉ số nhỏ nhất (0). 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 j), hãy kiểm tra lại với aaaa và abab.
  • So sánh char có dấu. Với byte ≥128 (UTF-8) hoặc dãy số được nén thành char, char có dấu làm thứ tự sai. Dùng unsigned char hoặc vector<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 w1≥w2≥⋯; 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 b trong a+a bằng Z-function hoặc KMP.
  • Đếm từ Lyndon và vòng cổ. Số từ Lyndon độ dài n trên bảng chữ cái k ký tự là

    Lk(n)=1n∑d∣nμ(d)kn/d,

    với μ là hàm Möbius. Mỗi vòng cổ (lớp xoay) độ dài n tương ứng đúng một từ Lyndon độ dài d∣n (xoay vòng nhỏ nhất của nó là wn/d), nên số vòng cổ là Nk(n)=∑d∣nLk(d), khớp với kết quả của bổ đề Burnside. Ví dụ k=2: L=2,1,2,3,6,9 với n=1..6, còn N3(4)=L3(1)+L3(2)+L3(4)=3+3+18=24.

  • Sinh mọi từ Lyndon độ dài ≤n theo thứ tự từ điển (thuật toán Fredricksen-Kessler-Maiorana, Duval 1988): từ từ hiện tại w, lặp w cho đủ độ dài n, 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 n 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 last ở 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 O(n) 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 106, cài thẳng Duval trên s+s.
  • Đếm vòng cổ (cntnecklace) (Khó): đếm vòng cổ n hạt m màu; lời giải chính dùng Burnside, có thể đối chiếu với công thức ∑d∣nLm(d) qua đếm từ Lyndon.
  • Xoay vòng nhỏ nhất từ điển (lexrot) (Khó): cùng bài toán với N≤106, 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.

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0