Cấu trúc hậu tố · Suffix Structures

Mọi xâu con là tiền tố của một hậu tố. Mảng hậu tố sắp mọi hậu tố theo thứ tự từ điển, nên các lần xuất hiện của một mẫu nằm liền nhau; mảng LCP cho độ dài tiền tố chung của hai hậu tố kề nhau. Từ hai mảng này ra đếm xâu con phân biệt, đoạn lặp dài nhất, đoạn chung của nhiều xâu. Ôtômat hậu tố là cấu trúc bổ sung: một đồ thị $O(n)$ trạng thái nhận đúng các xâu con, tiện cho bài đếm số lần xuất hiện.

Mảng hậu tố bằng nhân đôi

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.

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 là 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 ô.

C++

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.

C++

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.

C++

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.

C++

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++;
}

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Inputcacao

Output1 3 0 2 4

Mỗi bước $O(n)$ , có $O(\log n)$ bước.

Mảng LCP và thuật toán Kasai

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

Hỏi nhanh

Xâu aaaa có bao nhiêu xâu con phân biệt?

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.

C++

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.

C++

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

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Inputababa

Output9

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

Ví dụĐoạn Lặp Dài Nhất

Đề. Xâu dài tới $10^5$ . In một xâu con dài nhất xuất hiện ở ít nhất hai vị trí (được chồng lấn), hoặc $-1$ .

Lời giải. Xâu con xuất hiện ít nhất hai lần là tiền tố chung của hai hậu tố khác nhau. LCP của hai hậu tố bất kỳ là cực tiểu lcp trên đoạn giữa chúng trong mảng hậu tố, nên không vượt lcp của một cặp kề nào đó. Vậy độ dài lớn nhất là lcp lớn nhất, và xâu cần in là tiền tố dài chừng ấy của hậu tố ở vị trí đó. buildSA, buildLCP như các ví dụ trước.

best là vị trí có lcp lớn nhất; lcp[0] = 0 nên khởi đầu best = 0 ổn. Không có lcp dương nghĩa là mọi ký tự khác nhau, in $-1$ .

C++

int best = 0;
for (int i = 1; i < n; i++)
    if (lcp[i] > lcp[best]) best = i;
if (lcp[best] == 0) cout << -1 << '\n';
else cout << s.substr(sa[best], lcp[best]) << '\n';

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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();
    int best = 0;
    for (int i = 1; i < n; i++)
        if (lcp[i] > lcp[best]) best = i;
    if (lcp[best] == 0) cout << -1 << '\n';
    else cout << s.substr(sa[best], lcp[best]) << '\n';
}

Inputbanana

Outputana

$O(n \log n)$ .

Tìm mẫu trên mảng hậu tố

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$ ; khi hậu tố ngắn hơn $|P|$ , đ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$ .

C++

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

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
    }
}

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

C++

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

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Inputabacaba
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]$ .

Hỏi nhanh

Trong ôtômat hậu tố của ababa, xâu aba xuất hiện bao nhiêu lần, tức endpos của trạng thái chứa nó có mấy phần tử?

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.

C++

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.

C++

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]);

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Inputababa

Output3
2
2
1
1

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

Khi đi thi

Đếm xâu con phân biệt, xâu con thứ $k$ , đoạn lặp, đoạn chung: mảng hậu tố + LCP, $O(n \log n)$ . Nhớ LCP của hai hậu tố bất kỳ là cực tiểu đoạn LCP giữa chúng (dựng bảng thưa nếu cần hỏi nhiều).
Nhiều xâu: ghép với ký tự phân cách riêng, đánh dấu mỗi hậu tố thuộc xâu nào; điều kiện “xuất hiện trong đủ $k$ xâu” thành cửa sổ trượt trên mảng hậu tố.
Đếm số lần xuất hiện theo lớp, đoạn chung với một xâu dài: ôtômat hậu tố, $2n$ trạng thái, cộng endpos theo len giảm dần.

Tóm tắt

Nhân đôi: hạng đoạn $2k$ là thứ tự cặp hạng hai nửa; sắp đếm cho $O(n \log n)$ .
Kasai: LCP kề nhau trong $O(n)$ , vì LCP chỉ giảm tối đa 1 khi sang vị trí kế tiếp.
Số xâu con phân biệt $= \frac{n(n+1)}{2} - \sum lcp$ ; mẫu chiếm một đoạn liên tiếp của mảng hậu tố.
Ôtômat hậu tố gom xâu con theo endpos; số lần xuất hiện là số vị trí kết thúc.

Bài tập

Tra Cứu Hạng Hậu Tốcanuc80k6201Dựng mảng hậu tố cho mỗi bộ, truy vấn hạng

q

chỉ là in sa[q].

LQDOJ

Mẫu Có Xuất Hiện?canuc80k6202Chặt nhị phân trên mảng hậu tố như ví dụ đếm mẫu, chỉ cần biết đoạn có rỗng không.

LQDOJ

Lần Xuất Hiện Đầucanuc80k6204Trong đoạn mảng hậu tố khớp mẫu, lấy vị trí nhỏ nhất bằng bảng thưa cực tiểu trên sa.

LQDOJ

Xâu Con Phân Biệt Thứ Kcanuc80k6207Duyệt mảng hậu tố, hậu tố thứ

j

thêm

n - sa_j - lcp_j

xâu mới theo đúng thứ tự từ điển; trừ dần

k

LQDOJ

Phân Bố Xâu Con Theo Độ Dàicanuc80k6208Hậu tố thứ

j

góp các độ dài từ

lcp_j + 1

tới

n - sa_j

; cộng một trên đoạn bằng mảng hiệu.

LQDOJ

Khôi Phục Từ Cột Cuốicanuc80k6209Biến đổi ngược: sắp ổn định cột cuối được cột đầu; đi theo ánh xạ giữa hai cột từ ký tự kết thúc.

LQDOJ

Liệt Kê Mọi Vị Trí Khớpcanuc80k6210Tìm đoạn mảng hậu tố của mẫu bằng chặt nhị phân, in các vị trí trong đoạn sau khi sắp tăng.

LQDOJ

Dựng Xâu Từ Thứ Tự Hậu Tốcanuc80k6212Đi theo mảng hậu tố, tăng ký tự khi hạng của hậu tố bắt đầu sau một vị trí không tăng; quá 26 ký tự thì không có xâu.

LQDOJ

Phép Quay Nhỏ Nhấtcanuc80k6213Dựng mảng hậu tố của

S + S

(hoặc chỉ sắp phép quay bằng nhân đôi vòng), lấy hậu tố nhỏ nhất bắt đầu trong nửa đầu.

LQDOJ

Đoạn Lặp Không Giao Nhaucanuc80k6214Chặt nhị phân

L

; các nhóm liên tiếp có LCP ít nhất

L

phải có hai vị trí cách nhau ít nhất

L

LQDOJ

Nhiều Truy Vấn Xâu Con Thứ Kcanuc80k6217Cộng dồn số xâu mới theo thứ tự mảng hậu tố, mỗi truy vấn chặt nhị phân tìm hậu tố chứa xâu thứ

k

LQDOJ

Đoạn Chung Của Mọi Xâucanuc80k6218Ghép các xâu với ký tự phân cách khác nhau; cửa sổ trượt trên mảng hậu tố chứa đủ mọi xâu, đáp án là cực tiểu LCP trong cửa sổ.

LQDOJ

Thông Điệp Lặp Ở Bên Phảicanuc80k6219Xuất hiện ít nhất

m

lần là

m

hậu tố liên tiếp; cực tiểu trên mọi cửa sổ

m - 1

giá trị LCP, lấy lớn nhất.

LQDOJ

Tổng Tiền Tố Chung Của Các Hậu Tốcanuc80k6220Tổng LCP mọi cặp với một hậu tố: mỗi cặp là cực tiểu trên đoạn LCP; ngăn xếp đơn điệu quét hai chiều.

LQDOJ

Mẫu Số Lặp Dài Nhấtcanuc80k6224Như bài

m

lần xuất hiện nhưng trên dãy số: nén giá trị rồi dựng mảng hậu tố của dãy.

LQDOJ

Giai Điệu Lặp Không Giao Nhaucanuc80k6225Lấy hiệu hai nốt kề để bỏ chuyển giọng; chặt nhị phân độ dài, nhóm LCP phải có hai vị trí đủ xa để không giao nhau.

LQDOJ

Đọc thêm

Mảng hậu tốVNOI WikiNhân đôi, LCP và ứng dụng bằng tiếng Việt.
Suffix Arraycp-algorithmsDựng bằng sắp đếm và các ứng dụng LCP.
Suffix AutomatonVNOI WikiÔtômat hậu tố bằng tiếng Việt.
Suffix Automatoncp-algorithmsChứng minh số trạng thái, endpos và ứng dụng.
Suffix ArrayUSACO GuideBài luyện có lời giải.