KMP

Hàm tiền tố

Một viền (border) của xâu $s$ là một xâu khác rỗng, ngắn hơn $s$, vừa là tiền tố vừa là hậu tố của $s$. Xâu aabaabaa có ba viền: aabaa, aa và a. Đánh số từ 1 và gọi $\pi(i)$ là độ dài viền dài nhất của tiền tố $s[1..i]$, bằng 0 nếu không có viền. Với ababa, $\pi = (0, 0, 1, 2, 3)$: tiền tố dài 5 có viền dài nhất aba.

Tính chất then chốt: viền của một viền cũng là viền. Nếu $u$ là viền của $s$ và $v$ là viền của $u$ thì $v$ là tiền tố của $u$, nên là tiền tố của $s$; và là hậu tố của $u$, nên là hậu tố của $s$. Ngược lại, mọi viền ngắn hơn của $s$ cũng là viền của viền dài nhất. Vậy các viền của $s[1..i]$ chính là dãy $\pi(i), \pi(\pi(i)), \pi(\pi(\pi(i))), \dots$ cho tới 0; với aabaabaa là $5 \to 2 \to 1 \to 0$.

Tính $\pi$ từ trái sang phải. Giả sử đã có $\pi(1..i-1)$ và đặt $j = \pi(i - 1)$. Viền của $s[1..i]$ là một viền của $s[1..i-1]$ nối thêm $s_i$. Thử viền dài nhất trước: nếu $s_{j+1} = s_i$ thì $\pi(i) = j + 1$. Nếu không, thử viền dài nhất kế tiếp của $s[1..i-1]$, chính là $\pi(j)$, và cứ thế; về tới $j = 0$ mà vẫn không khớp thì $\pi(i) = 0$.

for (ll i = 2, j = 0; i <= n; i++) {
    while (j && s[i] != s[j + 1]) j = pi[j];
    if (s[i] == s[j + 1]) j++;
    pi[i] = j;
}

Dù có vòng while, tổng thời gian là $O(n)$. Biến $j$ tăng nhiều nhất 1 ở mỗi $i$, mỗi lần lùi làm $j$ giảm ít nhất 1, và $j$ không âm. Số lần giảm không thể vượt số lần tăng, tức không quá $n$.

Ví dụCác Viền Của Xâu

Đề. Cho xâu $S$ dài tới $10^6$. In độ dài mọi viền theo thứ tự tăng dần, không có viền thì in 0.

Lời giải. Tính $\pi$ của cả xâu, rồi đi theo dãy $\pi(n), \pi(\pi(n)), \dots$ tới 0: đó đúng là mọi viền, từ dài tới ngắn. Lưu lại rồi in ngược. Thử mọi độ dài và so hai đầu bằng tay là $O(n^2)$. Với aaaaa, $\pi(5) = 4$ và dãy là $4, 3, 2, 1$.

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

const ll N = 1e6 + 5;
ll n, pi[N];
string s;

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

    cin >> s;
    n = s.size();
    s = " " + s;
    for (ll i = 2, j = 0; i <= n; i++) {
        while (j && s[i] != s[j + 1]) j = pi[j];
        if (s[i] == s[j + 1]) j++;
        pi[i] = j;
    }
    vector<ll> v;
    for (ll k = pi[n]; k; k = pi[k]) v.push_back(k);
    reverse(v.begin(), v.end());
    if (v.empty()) cout << 0;
    for (ll x : v) cout << x << ' ';
    cout << '\n';
}

ChạyInputaaaaa

Output1 2 3 4

Tìm mẫu

Quét văn bản $T$ từ trái sang, giữ $j$ là số ký tự đầu của $P$ khớp với hậu tố dài nhất của phần văn bản đã đọc. Đọc thêm $T_i$: nếu $P_{j+1} = T_i$ thì $j$ tăng; nếu không, phần khớp mới phải là một viền của $P[1..j]$ nối thêm $T_i$, nên lùi $j \gets \pi(j)$ và thử lại, đúng như lúc tính $\pi$. Khi $j = |P|$ là một lần xuất hiện kết thúc tại $i$; ghi nhận rồi đặt $j \gets \pi(|P|)$ để tiếp tục, chứ không về 0, nhờ vậy các lần xuất hiện chồng lấn không bị bỏ sót.

Con trỏ $i$ chạy đúng một lượt qua văn bản, còn $j$ tăng nhiều nhất 1 mỗi bước và mỗi lần lùi giảm ít nhất 1.

Độ phức tạp: tổng thời gian là $O(|T| + |P|)$ kể cả tính $\pi$, bộ nhớ $O(|P|)$.

Một mẹo cài gọn: tính $\pi$ của xâu ghép $P + \# + T$, với # không xuất hiện trong hai xâu; vị trí nào trong phần $T$ có $\pi = |P|$ là một lần xuất hiện. KMP chỉ cần so hai phần tử bằng nhau, nên chạy được trên dãy số hay bất cứ thứ gì so sánh được.

Khác biệt với cách thử từng vị trí lớn nhất ở những xâu lặp nhiều:

KMP nhanh gấp hàng trăm lần. Cách thử từng vị trí chỉ đủ nhanh khi mẫu rất ngắn.

Ví dụĐếm Lần Khớp

Đề. Cho văn bản $T$ và mẫu $P$, mỗi xâu dài tới $10^6$. Đếm số lần $P$ xuất hiện trong $T$, kể cả chồng lấn.

Lời giải. Tính $\pi$ trên mẫu, quét văn bản như trên, mỗi lần $j$ chạm $|P|$ thì đếm và lùi về $\pi(|P|)$. Đặt $j$ về 0 sau mỗi lần khớp là lỗi kinh điển: với aaa trong aaaaa nó đếm 1 thay vì 3. Hai xâu đánh số từ 1 bằng cách thêm một ký tự đệm ở đầu. Với ví dụ, mỗi khối năm chữ a có ba vị trí khớp, tổng 6.

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

const ll N = 1e6 + 5;
ll pi[N];
string t, p;

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

    cin >> t >> p;
    ll n = t.size(), m = p.size();
    t = " " + t;
    p = " " + p;
    for (ll i = 2, j = 0; i <= m; i++) {
        while (j && p[i] != p[j + 1]) j = pi[j];
        if (p[i] == p[j + 1]) j++;
        pi[i] = j;
    }
    ll ans = 0;
    for (ll i = 1, j = 0; i <= n; i++) {
        while (j && t[i] != p[j + 1]) j = pi[j];
        if (t[i] == p[j + 1]) j++;
        if (j == m) {
            ans++;
            j = pi[j];
        }
    }
    cout << ans << '\n';
}

ChạyInputaaaaabaaaaa
aaa

Output6

Chu kỳ và cây viền

Số $k$ là một chu kỳ của xâu $s$ dài $n$ nếu $s_i = s_{i+k}$ với mọi $i$ hợp lệ, tức dịch $s$ sang phải $k$ ô thì phần chồng lên nhau trùng khớp. Xâu có chu kỳ $k$ khi và chỉ khi nó có viền dài $n - k$: phần chồng lên nhau chính là tiền tố và hậu tố dài $n - k$. Vì vậy chu kỳ ngắn nhất là $n - \pi(n)$, ứng với viền dài nhất. Chẳng hạn một thông điệp lặp vô hạn mà ta chỉ thấy $L$ ký tự đầu thì dài ít nhất $L - \pi(L)$, và $L$ không cần chia hết cho độ dài ấy.

Chu kỳ chưa chắc chia hết độ dài: abcabca có chu kỳ 3 dù dài 7. Xâu là $t$ lặp nguyên vẹn $c \ge 2$ lần khi và chỉ khi chu kỳ ngắn nhất $k$ chia hết $n$ và $k < n$; khi đó số lần lặp lớn nhất là $n / k$. Điều này đúng nhờ một bổ đề quen: nếu $k$ là chu kỳ nhỏ nhất và một chu kỳ $d$ chia hết $n$ thì $k$ cũng chia hết $d$, nên không có cách lặp nào “thô” hơn bị bỏ sót.

Cây viền. Nối mỗi độ dài $k \ge 1$ với cha $\pi(k)$ ta được một cây gốc 0: mỗi số có đúng một cha nhỏ hơn nó, đi theo cha mãi sẽ về 0. Các số gặp trên đường từ $k$ về 0 là tổ tiên của $k$; các số đi theo cha sẽ qua $k$ (kể cả $k$) tạo thành cây con của $k$. Các viền của tiền tố dài $k$ là các tổ tiên của $k$. Ngược lại, tiền tố dài $k$ xuất hiện kết thúc tại vị trí $i$ khi và chỉ khi $k$ là một viền của $s[1..i]$ (hoặc chính $s[1..i]$), tức $k$ là tổ tiên của $i$. Vậy số lần tiền tố dài $k$ xuất hiện trong $s$ bằng số nút trong cây con của $k$, tính được bằng cách cộng dồn $\mathrm{cnt}[\pi(i)] \mathrel{+}= \mathrm{cnt}[i]$ với $i$ giảm dần, xuất phát từ $\mathrm{cnt}[i] = 1$.

Ví dụChu Kỳ Của Các Tiền Tố

Đề. Nhiều test (tổng độ dài $10^6$). Với mỗi xâu $S$, liệt kê theo độ dài tăng dần mọi tiền tố là một xâu ngắn hơn lặp nguyên vẹn ít nhất 2 lần, kèm số lần lặp lớn nhất. Mỗi test in dòng Test case #x rồi một dòng trống ở cuối.

Lời giải. Với tiền tố dài $i$, chu kỳ ngắn nhất là $k = i - \pi(i)$. Tiền tố là lặp khi $\pi(i) > 0$ và $k$ chia hết $i$; số lần lặp là $i / k$. Một lượt tính $\pi$ trả lời mọi tiền tố, $O(n)$. Với ababab, $\pi(4) = 2$ cho $4 = 2 \cdot 2$ và $\pi(6) = 4$ cho $6 = 3 \cdot 2$; $\pi(5) = 3$ có chu kỳ 2 không chia hết 5.

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

const ll N = 1e6 + 5;
ll pi[N];

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

    ll T;
    cin >> T;
    for (ll tc = 1; tc <= T; tc++) {
        ll n;
        string s;
        cin >> n >> s;
        s = " " + s;
        for (ll i = 2, j = 0; i <= n; i++) {
            while (j && s[i] != s[j + 1]) j = pi[j];
            if (s[i] == s[j + 1]) j++;
            pi[i] = j;
        }
        cout << "Test case #" << tc << '\n';
        for (ll i = 2; i <= n; i++) {
            ll k = i - pi[i];
            if (pi[i] && i % k == 0) cout << i << ' ' << i / k << '\n';
        }
        cout << '\n';
    }
}

ChạyInput1
6
ababab

OutputTest case #1
4 2
6 3

Dãy số, xâu vòng

Dãy sai khác một hằng số. Muốn biết đoạn $a[l..l+m-1]$ có bằng $b$ cộng một hằng số không, so hai dãy hiệu kề nhau: cộng cùng một số không đổi hiệu, và hai dãy có cùng dãy hiệu thì sai khác một hằng số. Bài thành tìm dãy hiệu của $b$ trong dãy hiệu của $a$ bằng KMP trên số nguyên, nhớ trường hợp $m = 1$ có dãy hiệu rỗng và khớp mọi vị trí.

Xâu vòng. Các phép xoay của $A$ là các đoạn dài $|A|$ của $A + A$. Hỏi $B$ có phải một phép xoay của $A$ không, hay có bao nhiêu điểm bắt đầu trên vòng cho ra $B$, là tìm $B$ trong $A + A$ (bỏ ký tự cuối để không đếm trùng điểm đầu). Với các tập điểm trên vòng tròn, như vạch trên mặt đồng hồ, ta sắp các điểm rồi lấy khoảng cách giữa hai điểm liên tiếp theo vòng: quay cả hình không đổi các khoảng cách, chỉ xoay vòng dãy của chúng.

Ví dụHai Mặt Số Không Mốc

Đề. Hai hình, mỗi hình có $n \le 2 \cdot 10^5$ vạch ở các góc nguyên khác nhau trong $[0, 360000)$. Hỏi có quay được hình thứ nhất (theo modulo 360000) để hai tập vạch trùng nhau không; in possible hoặc impossible.

Lời giải. Sắp góc của mỗi hình, lấy dãy khoảng cách theo vòng $d_i = a_{i+1} - a_i$ và $d_n = a_1 + 360000 - a_n$. Quay hình là cộng cùng một góc vào mọi vạch, nên tập vạch của hình thứ nhất sau khi quay trùng hình thứ hai khi và chỉ khi dãy khoảng cách của hình hai là một phép xoay vòng của dãy khoảng cách hình một. Tìm dãy của hình hai trong dãy hình một viết hai lần bằng KMP trên số nguyên, $O(n)$ sau khi sắp. Với ví dụ, cả hai dãy đều là $(90000, 90000, 90000, 90000)$.

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

const ll N = 2e5 + 5, M = 360000;
ll n, a[N], b[N], t[2 * N], p[N], pi[N];

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

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (ll i = 1; i <= n; i++) {
        t[i] = t[i + n] = (i < n ? a[i + 1] - a[i] : a[1] + M - a[n]);
        p[i] = (i < n ? b[i + 1] - b[i] : b[1] + M - b[n]);
    }
    for (ll i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1]) j = pi[j];
        if (p[i] == p[j + 1]) j++;
        pi[i] = j;
    }
    bool ok = 0;
    for (ll i = 1, j = 0; i < 2 * n && !ok; i++) {
        while (j && t[i] != p[j + 1]) j = pi[j];
        if (t[i] == p[j + 1]) j++;
        if (j == n) ok = 1;
    }
    cout << (ok ? "possible" : "impossible") << '\n';
}

ChạyInput4
0 90000 180000 270000
45000 135000 225000 315000

Outputpossible

Tự động KMP

Trạng thái $j$ của KMP, “đang khớp $j$ ký tự đầu của mẫu”, gói gọn mọi thứ cần biết về phần văn bản đã đọc để quyết định mẫu có xuất hiện tiếp hay không. Tính sẵn bảng chuyển $\mathrm{go}[j][c]$: từ trạng thái $j < |P|$ đọc chữ $c$ thì sang trạng thái nào. Bảng tính được trong $O(|P| \cdot \Sigma)$, với $\Sigma$ là số chữ cái, bằng chính quy tắc lùi: $\mathrm{go}[j][c] = j + 1$ nếu $P_{j+1} = c$, ngược lại bằng $\mathrm{go}[\pi(j)][c]$ (với $\mathrm{go}[0][c] = 0$ khi $c \ne P_1$). Đây là một tự động (automaton) hữu hạn có $|P| + 1$ trạng thái.

Chính bảng này cũng làm KMP chạy nhanh hơn: mỗi ký tự văn bản chỉ tra một lần, không còn vòng while.

Bảng chuyển nhanh gấp khoảng 2,5 lần khi bảng chữ cái nhỏ. Bảng chữ cái 26 chữ thì bảng $|P| \cdot 26$ ô cũng tốn bộ nhớ, nên chỉ dựng khi cần làm trạng thái quy hoạch động.

Tự động này làm trạng thái cho quy hoạch động trên xâu: đếm xâu độ dài $n$ chứa (hoặc không chứa) mẫu, xâu con chung dài nhất tránh một mẫu cấm, điền ký tự để mẫu xuất hiện nhiều nhất. $\mathrm{dp}[i][j]$ là số cách viết $i$ ký tự đầu mà tự động đang ở trạng thái $j$; thêm một chữ là đi theo $\mathrm{go}$. Đây cũng là khuôn của quy hoạch động chữ số (bài 13) với trạng thái là một tự động, và mở rộng tự nhiên sang nhiều mẫu với Aho-Corasick (bài 73).

Ví dụĐếm Xâu Có Mẫu Bắt Buộc

Đề. Cho $N \le 1000$ và mẫu chữ hoa $P$ ($|P| \le 100$). Đếm số xâu độ dài $N$ trên 26 chữ hoa có chứa $P$ ít nhất một lần, theo modulo $10^9 + 7$.

Lời giải. Đếm bù: lấy $26^N$ trừ số xâu không chứa $P$. Đọc một xâu từng chữ qua tự động KMP của $P$; xâu không chứa $P$ khi và chỉ khi trạng thái chưa bao giờ chạm $|P|$. Vậy chỉ cần đếm số xâu theo trạng thái hiện tại. Với $N = 3$ và AB: có $26^3 = 17576$ xâu, trong đó 52 xâu chứa AB (26 xâu dạng ABx và 26 xâu dạng xAB, không xâu nào thuộc cả hai).

Bước 1: hàm tiền tố của mẫu. Như mọi bài KMP, mẫu đánh số từ 1 nhờ ký tự đệm ở đầu.

for (ll i = 2, j = 0; i <= m; i++) {
    while (j && p[i] != p[j + 1]) j = pi[j];
    if (p[i] == p[j + 1]) j++;
    pi[i] = j;
}

Bước 2: bảng chuyển của tự động. go[j][c] là trạng thái mới khi đang ở $j$ (đã khớp $j$ ký tự đầu của mẫu) và đọc chữ $c$. Khớp ký tự kế thì lên $j + 1$; không khớp thì đi như từ trạng thái $\pi(j)$, đã tính xong vì $\pi(j) < j$. Bảng biến mỗi bước của KMP thành một lần tra, không còn vòng while.

for (ll j = 0; j < m; j++)
    for (ll c = 0; c < 26; c++) {
        if (p[j + 1] - 'A' == c) go[j][c] = j + 1;
        else go[j][c] = j ? go[pi[j]][c] : 0;
    }

Bước 3: đếm theo trạng thái. $\mathrm{dp}[j]$ là số xâu đã dựng có trạng thái $j < |P|$. Thêm một chữ: mọi xâu ở $j$ đi sang go[j][c] với 26 chữ $c$; chuyển nào chạm $|P|$ thì bỏ, vì xâu đó đã chứa mẫu. Song song tính $26^N$.

for (ll i = 0; i < n; i++) {
    all = all * 26 % MOD;
    for (ll j = 0; j < m; j++) nd[j] = 0;
    for (ll j = 0; j < m; j++)
        for (ll c = 0; c < 26; c++)
            if (go[j][c] < m) nd[go[j][c]] = (nd[go[j][c]] + dp[j]) % MOD;
    for (ll j = 0; j < m; j++) dp[j] = nd[j];
}

Đáp án là $26^N$ trừ tổng các $\mathrm{dp}[j]$, cộng thêm MOD để không âm.

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

const ll MOD = 1e9 + 7;
ll n, m, pi[105], go[105][26], dp[105], nd[105];
string p;

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

    cin >> n >> p;
    m = p.size();
    p = " " + p;
    for (ll i = 2, j = 0; i <= m; i++) {
        while (j && p[i] != p[j + 1]) j = pi[j];
        if (p[i] == p[j + 1]) j++;
        pi[i] = j;
    }
    for (ll j = 0; j < m; j++)
        for (ll c = 0; c < 26; c++) {
            if (p[j + 1] - 'A' == c) go[j][c] = j + 1;
            else go[j][c] = j ? go[pi[j]][c] : 0;
        }
    dp[0] = 1;
    ll all = 1;
    for (ll i = 0; i < n; i++) {
        all = all * 26 % MOD;
        for (ll j = 0; j < m; j++) nd[j] = 0;
        for (ll j = 0; j < m; j++)
            for (ll c = 0; c < 26; c++)
                if (go[j][c] < m) nd[go[j][c]] = (nd[go[j][c]] + dp[j]) % MOD;
        for (ll j = 0; j < m; j++) dp[j] = nd[j];
    }
    ll bad = 0;
    for (ll j = 0; j < m; j++) bad = (bad + dp[j]) % MOD;
    cout << (all - bad + MOD) % MOD << '\n';
}

ChạyInput3
AB

Output52

Chi phí $N \cdot |P| \cdot 26 \approx 2{,}6 \cdot 10^6$.