Suffix Structures

Mảng hậu tố

sa[j] là vị trí bắt đầu của hậu tố đứng thứ $j$. Nhân đôi: giả sử đã có hạng rk[i] của đoạn dài $k$ bắt đầu tại $i$ (đoạn có thể bị cắt ở cuối xâu). Đoạn dài $2k$ tại $i$ so sánh được bằng cặp $(rk_i, rk_{i+k})$, với $rk_{i+k} = -1$ khi $i + k \ge n$. Sắp các cặp, đánh lại hạng, gấp đôi $k$; dừng khi mọi hạng khác nhau.

Sắp cặp bằng sắp đếm hai lượt (khóa phụ trước, khóa chính sau) để mỗi vòng $O(n)$, tổng $O(n \log n)$. Khóa phụ có sẵn thứ tự: các vị trí $i \ge n - k$ (khóa phụ $-1$) đứng đầu, rồi $sa_j - k$ theo thứ tự của mảng hậu tố vòng trước.

Trong hình, mỗi hàng là một hậu tố theo thứ tự hiện tại; xanh dương là nửa đầu dài $k$, cam là nửa sau. Bước cuối cho mảng LCP.

Ví dụThứ Tự Các Hậu Tố

Đề. Xâu chữ thường dài tới $5 \cdot 10^5$. In mảng hậu tố, vị trí đánh số từ 0.

Lời giải. Nhân đôi độ dài so sánh: sau bước $k$, rk[i] là hạng của $k$ ký tự đầu của hậu tố $i$ (hậu tố ngắn hơn $k$ thì so cả hậu tố). Thứ tự theo $2k$ ký tự đầu là thứ tự theo cặp (rk[i], rk[i + k]), cặp thiếu nửa sau coi nửa sau là nhỏ nhất. Sắp cặp bằng hai lượt: theo khóa phụ trước, rồi sắp đếm ổn định theo khóa chính. Dừng khi mọi hạng đã khác nhau.

Bước 1: sắp theo ký tự đầu. Hạng ban đầu là mã ký tự nên lượt đếm đầu dùng 128 ô.

for (int i = 0; i < n; i++) cnt[rk[i] = s[i]]++;
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;

Bước 2: sắp theo khóa phụ, không cần đếm. Các hậu tố $i \ge n - k$ không có nửa sau nên đứng đầu. Các hậu tố còn lại có nửa sau là hậu tố $i + k$, mà sa đã sắp theo đúng khóa đó; duyệt sa và lấy sa[i] - k là xong.

int p = 0;
for (int i = n - k; i < n; i++) tp[p++] = i;
for (int i = 0; i < n; i++)
    if (sa[i] >= k) tp[p++] = sa[i] - k;

Bước 3: sắp đếm ổn định theo khóa chính. Duyệt tp từ cuối: hậu tố cùng khóa chính giữ đúng thứ tự khóa phụ. Giờ sa đã sắp theo $2k$ ký tự đầu.

for (int i = 0; i < m; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[rk[i]]++;
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tp[i]]]] = tp[i];

Bước 4: hạng mới. swap(rk, tp): tp giữ hạng cũ, rk được tính lại. Hai hậu tố kề nhau trong sa cùng hạng mới khi cả khóa chính lẫn khóa phụ bằng nhau; khóa phụ thiếu ghi $-1$. p là số hạng khác nhau: p == n thì dừng, ngược lại m = p cho lượt đếm sau.

swap(rk, tp);
rk[sa[0]] = 0, p = 1;
for (int i = 1; i < n; i++) {
    int a = sa[i], b = sa[i - 1];
    int x = a + k < n ? tp[a + k] : -1, y = b + k < n ? tp[b + k] : -1;
    rk[a] = tp[a] == tp[b] && x == y ? p - 1 : p++;
}

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

const int N = 5e5 + 5;
int n, sa[N], rk[N], tp[N], cnt[N];
string s;

void buildSA() {
    int m = 128;
    for (int i = 0; i < n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
    for (int k = 1;; k <<= 1) {
        int p = 0;
        for (int i = n - k; i < n; i++) tp[p++] = i;
        for (int i = 0; i < n; i++)
            if (sa[i] >= k) tp[p++] = sa[i] - k;
        for (int i = 0; i < m; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[i]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tp[i]]]] = tp[i];
        swap(rk, tp);
        rk[sa[0]] = 0, p = 1;
        for (int i = 1; i < n; i++) {
            int a = sa[i], b = sa[i - 1];
            int x = a + k < n ? tp[a + k] : -1, y = b + k < n ? tp[b + k] : -1;
            rk[a] = tp[a] == tp[b] && x == y ? p - 1 : p++;
        }
        if (p == n) break;
        m = p;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    n = s.size();
    buildSA();
    for (int i = 0; i < n; i++) cout << sa[i] << ' ';
    cout << '\n';
}

ChạyInputcacao

Output1 3 0 2 4

Mỗi bước $O(n)$, có $O(\log n)$ bước. Chỗ “sắp đếm” tưởng nhỏ, nhưng thay nó bằng sort thì thêm một hệ số $\log n$ và hằng số cũng nặng hơn:

Sắp đếm nhanh hơn gọi sort mỗi vòng khoảng 6 lần. Xâu càng ít loại ký tự, càng nhiều vòng nhân đôi, khoảng cách càng lớn. Quy tắc: dựng mảng hậu tố cho $n$ từ vài trăm nghìn thì dùng sắp đếm.

Mảng LCP

lcp[j] là độ dài tiền tố chung của hai hậu tố sa[j-1] và sa[j]. Kasai duyệt vị trí $i$ theo thứ tự trong xâu: nếu hậu tố $i$ có LCP bằng $h$ với hậu tố đứng ngay trước nó, thì hậu tố $i + 1$ có LCP ít nhất $h - 1$ với hậu tố đứng ngay trước nó (bỏ ký tự đầu của cả hai). Biến $h$ chỉ giảm tối đa $n$ lần nên tổng $O(n)$.

Hai hệ quả dùng nhiều nhất:

• LCP của hai hậu tố bất kỳ là cực tiểu của lcp trên đoạn giữa chúng trong mảng hậu tố.
• Hậu tố sa[j] đóng góp $n - sa_j - lcp_j$ xâu con mới (các tiền tố dài hơn $lcp_j$), nên số xâu con phân biệt là $\frac{n(n+1)}{2} - \sum lcp_j$.

Ví dụĐếm Xâu Con Khác Nhau

Đề. Xâu chữ thường dài tới $10^5$. Đếm số xâu con liên tiếp phân biệt.

Lời giải. Mỗi xâu con là tiền tố của một hậu tố. Duyệt các hậu tố theo thứ tự mảng hậu tố: hậu tố sa[j] có $n - sa_j$ tiền tố, trong đó $lcp_j$ tiền tố đầu đã xuất hiện ở hậu tố đứng trước. Các tiền tố dài hơn $lcp_j$ là mới, vì xâu con nào lặp lại cũng phải là tiền tố chung với hậu tố kề trước theo thứ tự. Tổng là $\frac{n(n+1)}{2} - \sum lcp$. buildSA giống hệt ví dụ trước.

Bước 1: mảng LCP bằng Kasai. rk dựng lại thành nghịch đảo của sa. Duyệt hậu tố theo vị trí $i$ trong xâu, so với hậu tố đứng ngay trước nó trong sa. h không cần đếm lại từ 0: bỏ ký tự đầu của hai hậu tố cặp trước cho hai hậu tố có tiền tố chung ít nhất $h - 1$, và hậu tố đứng ngay trước $i + 1$ trong sa chỉ có thể chung nhiều hơn. h giảm tối đa $n$ lần nên vòng while chạy tổng $O(n)$. Hậu tố đứng đầu sa không có hậu tố trước, đặt h = 0.

void buildLCP() {
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    for (int i = 0, h = 0; i < n; i++) {
        if (rk[i] == 0) {
            h = 0;
            continue;
        }
        if (h) h--;
        int j = sa[rk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[rk[i]] = h;
    }
}

Bước 2: đáp án. Tới $\frac{10^5 \cdot (10^5 + 1)}{2} \approx 5 \cdot 10^9$ nên dùng long long.

ll ans = (ll)n * (n + 1) / 2;
for (int i = 1; i < n; i++) ans -= lcp[i];

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

const int N = 1e5 + 5;
int n, sa[N], rk[N], tp[N], cnt[N], lcp[N];
string s;

void buildSA() {
    int m = 128;
    for (int i = 0; i < n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
    for (int k = 1;; k <<= 1) {
        int p = 0;
        for (int i = n - k; i < n; i++) tp[p++] = i;
        for (int i = 0; i < n; i++)
            if (sa[i] >= k) tp[p++] = sa[i] - k;
        for (int i = 0; i < m; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[i]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tp[i]]]] = tp[i];
        swap(rk, tp);
        rk[sa[0]] = 0, p = 1;
        for (int i = 1; i < n; i++) {
            int a = sa[i], b = sa[i - 1];
            int x = a + k < n ? tp[a + k] : -1, y = b + k < n ? tp[b + k] : -1;
            rk[a] = tp[a] == tp[b] && x == y ? p - 1 : p++;
        }
        if (p == n) break;
        m = p;
    }
}

void buildLCP() {
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    for (int i = 0, h = 0; i < n; i++) {
        if (rk[i] == 0) {
            h = 0;
            continue;
        }
        if (h) h--;
        int j = sa[rk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[rk[i]] = h;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    n = s.size();
    buildSA();
    buildLCP();
    ll ans = (ll)n * (n + 1) / 2;
    for (int i = 1; i < n; i++) ans -= lcp[i];
    cout << ans << '\n';
}

ChạyInputababa

Output9

$O(n \log n)$ cho mảng hậu tố, $O(n)$ cho LCP.

Tìm mẫu

Các hậu tố có tiền tố $P$ tạo thành một đoạn liên tiếp trong mảng hậu tố. Đầu đoạn là hậu tố nhỏ nhất không nhỏ hơn $P$ (so $|P|$ ký tự đầu), cuối đoạn là hậu tố cuối cùng có $|P|$ ký tự đầu bằng $P$. Hai lần chặt nhị phân, mỗi lần so sánh tốn $O(|P|)$: một mẫu tốn $O(|P| \log n)$, không phụ thuộc số lần xuất hiện.

s.compare(pos, len, P) so đoạn $s[pos, pos + len)$ với $P$. Hậu tố ngắn hơn $|P|$ thì đoạn bị cắt và vẫn so đúng thứ tự từ điển.

Ví dụĐếm Vị Trí Của Mẫu

Đề. Văn bản dài tới $10^5$, tới $5 \cdot 10^5$ mẫu, tổng độ dài mẫu tới $5 \cdot 10^5$. Đếm số lần xuất hiện (được chồng lấn) của từng mẫu.

Lời giải. Các hậu tố có tiền tố $P$ nằm liền một đoạn trong mảng hậu tố. Đầu đoạn là hậu tố đầu tiên có $|P|$ ký tự đầu không nhỏ hơn $P$; cuối đoạn cộng 1 là hậu tố đầu tiên có $|P|$ ký tự đầu lớn hơn $P$. Hai lần chặt nhị phân, hiệu hai kết quả là số lần xuất hiện. Chặt được vì theo thứ tự mảng hậu tố, kết quả so với $P$ chỉ đổi từ “nhỏ hơn” sang “bằng” sang “lớn hơn” một lần. buildSA như ví dụ đầu.

Bước 1: một lần chặt. s.compare(sa[mid], p.size(), p) so đoạn bắt đầu ở sa[mid] dài tối đa $|P|$ với $P$; hậu tố ngắn hơn $|P|$ bị cắt ngắn và vẫn so đúng thứ tự từ điển. strict = 1 tìm vị trí đầu tiên lớn hơn $P$, strict = 0 tìm vị trí đầu tiên không nhỏ hơn $P$; không có thì trả $n$.

int bound(string &p, int strict) {
    int l = 0, r = n - 1, res = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        int c = s.compare(sa[mid], p.size(), p);
        if (c > 0 || (c == 0 && !strict)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}

Bước 2: đếm. bound(p, 1) - bound(p, 0).

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

const int N = 1e5 + 5;
int n, sa[N], rk[N], tp[N], cnt[N];
string s;

void buildSA() {
    int m = 128;
    for (int i = 0; i < n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
    for (int k = 1;; k <<= 1) {
        int p = 0;
        for (int i = n - k; i < n; i++) tp[p++] = i;
        for (int i = 0; i < n; i++)
            if (sa[i] >= k) tp[p++] = sa[i] - k;
        for (int i = 0; i < m; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[i]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tp[i]]]] = tp[i];
        swap(rk, tp);
        rk[sa[0]] = 0, p = 1;
        for (int i = 1; i < n; i++) {
            int a = sa[i], b = sa[i - 1];
            int x = a + k < n ? tp[a + k] : -1, y = b + k < n ? tp[b + k] : -1;
            rk[a] = tp[a] == tp[b] && x == y ? p - 1 : p++;
        }
        if (p == n) break;
        m = p;
    }
}

int bound(string &p, int strict) {
    int l = 0, r = n - 1, res = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        int c = s.compare(sa[mid], p.size(), p);
        if (c > 0 || (c == 0 && !strict)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    n = s.size();
    buildSA();
    int k;
    cin >> k;
    while (k--) {
        string p;
        cin >> p;
        cout << bound(p, 1) - bound(p, 0) << '\n';
    }
}

ChạyInputaaaaa
4
a
aa
aaa
b

Output5
4
3
0

Mỗi mẫu $O(|P| \log n)$.

Ghép nhiều xâu

Đoạn chung của $A$ và $B$ là tiền tố chung của một hậu tố của $A$ và một hậu tố của $B$. Ghép $T = A + \# + B$ với ký tự phân cách không có trong cả hai xâu: LCP không thể vượt qua #, nên mọi tiền tố chung giữa hậu tố của $A$ và của $B$ trong $T$ đúng là đoạn chung. Đáp án là lcp[j] lớn nhất trên các cặp kề có một hậu tố bắt đầu trong $A$ và một trong $B$; cặp tốt nhất luôn kề nhau ở một chỗ nào đó vì LCP giữa hai hậu tố là cực tiểu đoạn giữa.

Nhiều xâu thì mỗi xâu một ký tự phân cách khác nhau, rồi chặt nhị phân độ dài hay dùng cửa sổ trượt trên mảng hậu tố sao cho đoạn chứa đủ các xâu cần có.

Ví dụĐộ Dài Đoạn Chung Dài Nhất

Đề. Hai xâu chữ thường, mỗi xâu dài tới $2.5 \cdot 10^5$. Tìm độ dài đoạn chung dài nhất.

Lời giải. Ghép $T = A + \text{`} + B$, với ` là ký tự đứng ngay trước a trong bảng mã và không có trong hai xâu. Tiền tố chung của hai hậu tố không thể vượt qua `, vì ký tự này chỉ xuất hiện một lần. Đoạn chung dài nhất là LCP lớn nhất giữa một hậu tố bắt đầu trong $A$ và một hậu tố bắt đầu trong $B$. buildSA, buildLCP như các ví dụ trước, trên xâu dài $|A| + |B| + 1$.

Bước 1: chỉ xét cặp kề khác phía. Lấy cặp tốt nhất $(a, b)$ ở hai phía. Trên đoạn mảng hậu tố giữa chúng có một chỗ đổi phía, và lcp ở đó không nhỏ hơn cực tiểu của cả đoạn, tức LCP của $(a, b)$. Hậu tố bắt đầu ngay ở ` được tính vào phía $B$, nhưng LCP của nó với mọi hậu tố khác là 0 nên không ảnh hưởng.

for (int i = 1; i < n; i++)
    if ((sa[i] < la) != (sa[i - 1] < la)) ans = max(ans, lcp[i]);

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

const int N = 5e5 + 5;
int n, sa[N], rk[N], tp[N], cnt[N], lcp[N];
string s;

void buildSA() {
    int m = 128;
    for (int i = 0; i < n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
    for (int k = 1;; k <<= 1) {
        int p = 0;
        for (int i = n - k; i < n; i++) tp[p++] = i;
        for (int i = 0; i < n; i++)
            if (sa[i] >= k) tp[p++] = sa[i] - k;
        for (int i = 0; i < m; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[i]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tp[i]]]] = tp[i];
        swap(rk, tp);
        rk[sa[0]] = 0, p = 1;
        for (int i = 1; i < n; i++) {
            int a = sa[i], b = sa[i - 1];
            int x = a + k < n ? tp[a + k] : -1, y = b + k < n ? tp[b + k] : -1;
            rk[a] = tp[a] == tp[b] && x == y ? p - 1 : p++;
        }
        if (p == n) break;
        m = p;
    }
}

void buildLCP() {
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    for (int i = 0, h = 0; i < n; i++) {
        if (rk[i] == 0) {
            h = 0;
            continue;
        }
        if (h) h--;
        int j = sa[rk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[rk[i]] = h;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string a, b;
    cin >> a >> b;
    s = a + '`' + b;
    n = s.size();
    int la = a.size();
    buildSA();
    buildLCP();
    int ans = 0;
    for (int i = 1; i < n; i++)
        if ((sa[i] < la) != (sa[i - 1] < la)) ans = max(ans, lcp[i]);
    cout << ans << '\n';
}

ChạyInputabacaba
zzacabx

Output4

$O(n \log n)$ với $n = |A| + |B| + 1$.

Ôtômat hậu tố

Ôtômat hậu tố của $S$ là DAG nhỏ nhất nhận đúng các xâu con của $S$: mỗi trạng thái là một lớp xâu con có cùng tập vị trí kết thúc (endpos). Trạng thái lưu len (độ dài dài nhất trong lớp), liên kết hậu tố lnk (trạng thái của hậu tố dài nhất có endpos khác) và các cung theo ký tự. Thêm từng ký tự vào cuối với thủ tục chuẩn có nhân bản trạng thái; tổng số trạng thái không quá $2n$.

Số lần xuất hiện của mọi xâu trong lớp $v$ là $|\text{endpos}(v)|$: đánh dấu 1 ở trạng thái vừa tạo khi thêm mỗi ký tự (không đánh dấu bản sao), rồi cộng dồn theo liên kết hậu tố từ trạng thái có len lớn tới nhỏ. Lớp $v$ chứa các xâu có độ dài trong $(len_{lnk_v}, len_v]$.

Ví dụTần Suất Lớn Nhất Theo Độ Dài

Đề. Xâu chữ thường dài $n \le 2.5 \cdot 10^5$. Với mỗi $L = 1..n$, in số lần xuất hiện lớn nhất của một xâu con dài $L$.

Lời giải. Dựng ôtômat hậu tố. Mọi xâu trong lớp $v$ xuất hiện đúng $occ_v = |\text{endpos}(v)|$ lần, và xâu dài nhất của lớp có độ dài $len_v$, nên trạng thái $v$ cho giá trị $occ_v$ ở độ dài $len_v$. Xâu dài $L$ xuất hiện $k$ lần thì mọi xâu con ngắn hơn của nó xuất hiện ít nhất $k$ lần. Vậy ghi ans[len] cho từng trạng thái rồi lấy cực đại hậu tố từ $L = n$ về 1.

Bước 1: thêm một ký tự. Trạng thái mới cur có occ = 1 vì nó ứng với một vị trí kết thúc mới. Đi theo liên kết hậu tố từ last, thêm cung c cho các trạng thái chưa có. Gặp trạng thái p đã có cung tới q: nếu len[q] == len[p] + 1 thì q là liên kết của cur; ngược lại tách q thành bản sao cl có độ dài đúng len[p] + 1. Bản sao có occ = 0, vì nó không ứng với vị trí kết thúc mới nào.

void extend(int c) {
    int cur = sz++, p = last;
    len[cur] = len[last] + 1, occ[cur] = 1;
    while (p != -1 && !nxt[p][c]) nxt[p][c] = cur, p = lnk[p];
    if (p == -1) lnk[cur] = 0;
    else {
        int q = nxt[p][c];
        if (len[p] + 1 == len[q]) lnk[cur] = q;
        else {
            int cl = sz++;
            len[cl] = len[p] + 1, lnk[cl] = lnk[q];
            memcpy(nxt[cl], nxt[q], sizeof(nxt[q]));
            while (p != -1 && nxt[p][c] == q) nxt[p][c] = cl, p = lnk[p];
            lnk[q] = lnk[cur] = cl;
        }
    }
    last = cur;
}

Bước 2: dồn occ theo liên kết. Sắp đếm các trạng thái theo len vào ord. Liên kết hậu tố luôn trỏ tới trạng thái có len nhỏ hơn, nên duyệt ord từ cuối thì mọi trạng thái đã nhận đủ occ trước khi cộng tiếp cho liên kết của mình. Cùng vòng đó ghi ans[len[v]]; gốc (độ dài 0) bị bỏ qua.

for (int i = sz - 1; i > 0; i--) {
    int v = ord[i];
    occ[lnk[v]] += occ[v];
    ans[len[v]] = max(ans[len[v]], occ[v]);
}
for (int L = n - 1; L >= 1; L--) ans[L] = max(ans[L], ans[L + 1]);

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

const int N = 5e5 + 5;
int sz, last, len[N], lnk[N], nxt[N][26], occ[N], cntLen[N], ord[N], ans[N];
string s;

void extend(int c) {
    int cur = sz++, p = last;
    len[cur] = len[last] + 1, occ[cur] = 1;
    while (p != -1 && !nxt[p][c]) nxt[p][c] = cur, p = lnk[p];
    if (p == -1) lnk[cur] = 0;
    else {
        int q = nxt[p][c];
        if (len[p] + 1 == len[q]) lnk[cur] = q;
        else {
            int cl = sz++;
            len[cl] = len[p] + 1, lnk[cl] = lnk[q];
            memcpy(nxt[cl], nxt[q], sizeof(nxt[q]));
            while (p != -1 && nxt[p][c] == q) nxt[p][c] = cl, p = lnk[p];
            lnk[q] = lnk[cur] = cl;
        }
    }
    last = cur;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    int n = s.size();
    sz = 1, last = 0, lnk[0] = -1;
    for (char ch : s) extend(ch - 'a');
    for (int v = 0; v < sz; v++) cntLen[len[v]]++;
    for (int i = 1; i <= n; i++) cntLen[i] += cntLen[i - 1];
    for (int v = sz - 1; v >= 0; v--) ord[--cntLen[len[v]]] = v;
    for (int i = sz - 1; i > 0; i--) {
        int v = ord[i];
        occ[lnk[v]] += occ[v];
        ans[len[v]] = max(ans[len[v]], occ[v]);
    }
    for (int L = n - 1; L >= 1; L--) ans[L] = max(ans[L], ans[L + 1]);
    for (int L = 1; L <= n; L++) cout << ans[L] << '\n';
}

ChạyInputababa

Output3
2
2
1
1

$O(26n)$ cho ôtômat, $O(n)$ cho phần còn lại.