Hàm tiền tố và thuật toán KMP

Hàm tiền tố (prefix function) $\pi$ của một xâu cho biết, tại mỗi vị trí $i$, độ dài đoạn đầu dài nhất của xâu, ngắn hơn $s[0..i]$, đồng thời kết thúc ở vị trí đó. Từ một mảng duy nhất này, thuật toán KMP (Knuth, Morris, Pratt) tìm mọi lần xuất hiện của mẫu $p$ (độ dài $m$) trong văn bản $t$ (độ dài $n$) trong $O(n+m)$, thay vì $O(n·m)$ của cách so từng vị trí. Cũng mảng đó trả lời được chu kỳ ngắn nhất của xâu, số lần xuất hiện của mọi tiền tố, và dựng được automaton KMP để quy hoạch động đếm các xâu không chứa mẫu.

Ý tưởng / Trực giác

Border và hàm tiền tố

Border (biên) của xâu $s$ là một xâu vừa là tiền tố vừa là hậu tố của $s$, nhưng không phải chính $s$. Ví dụ abacaba có các border a, aba (và xâu rỗng).

Định nghĩa (đánh chỉ số từ $0$):

$$\pi [i]=\text{độ dài border dài nhất của }s[0..i].$$

Theo định nghĩa $\pi [0]=0$. Ví dụ với $s=$ aabaaab:

 i    :  0  1  2  3  4  5  6
 s[i] :  a  a  b  a  a  a  b
 pi[i]:  0  1  0  1  2  2  3

$\pi [6]=3$ vì aab vừa là tiền tố của aabaaab, vừa là hậu tố của nó, và không có border nào dài hơn.

Tại sao KMP nhanh: không bao giờ lùi con trỏ văn bản

Cách ngây thơ đặt mẫu ở vị trí $0$, so tới khi lệch, rồi dịch mẫu sang một ô và so lại từ đầu. Nhưng khi đã khớp được $j$ ký tự $p[0..j-1]$ rồi mới lệch, ta đã biết $j$ ký tự cuối vừa đọc của văn bản chính là $p[0..j-1]$. Câu hỏi "dịch mẫu tới đâu thì phần đã đọc vẫn còn khớp?" chỉ phụ thuộc vào $p$, và câu trả lời là: dịch sao cho một border của $p[0..j-1]$ nằm đúng chỗ. Dịch ít nhất tương ứng với border dài nhất, tức giữ lại $\pi [j-1]$ ký tự đã khớp.

Vậy con trỏ trên văn bản chỉ tiến, còn "độ dài đang khớp" $j$ thì có lúc tăng $1$, có lúc tụt về $\pi [j-1]$.

Chuỗi các border lồng nhau

Hai tính chất then chốt:

1. Border của border cũng là border. Nếu $b$ là border của $s$ và $c$ là border của $b$ thì $c$ là tiền tố của $b$ (nên là tiền tố của $s$) và là hậu tố của $b$ (nên là hậu tố của $s$).
2. Mọi border của $s[0..i]$ đều nằm trong chuỗi $$\pi [i]>\pi [\pi [i]-1]>\pi [\pi [\pi [i]-1]-1]>\dots >0.$$ Lý do: gọi $k=\pi [i]$ là border dài nhất. Một border ngắn hơn $k^{\prime }<k$ của $s[0..i]$ là hậu tố của $s[0..i]$, nên cũng là hậu tố của border $s[i-k+1..i]=s[0..k-1]$; nó lại là tiền tố, nên nó là border của $s[0..k-1]$, và border dài nhất trong số đó có độ dài $\pi [k-1]$. Lặp lại lập luận.

Vì thế khi cần "border dài nhất tiếp theo ngắn hơn $j$" ta chỉ việc nhảy $j\leftarrow \pi [j-1]$, không phải thử mọi độ dài.

Tính $\pi [i]$ từ các giá trị trước

Một border của $s[0..i]$ có độ dài $k\ge 1$ thì bỏ ký tự cuối đi sẽ được một border (có thể rỗng) của $s[0..i-1]$ độ dài $k-1$, kèm điều kiện $s[k-1]=s[i]$. Do đó:

• Thử các border của $s[0..i-1]$ từ dài đến ngắn: $j=\pi [i-1]$, rồi $\pi [j-1]$, ...
• Dừng ở $j$ đầu tiên có $s[j]=s[i]$, khi đó $\pi [i]=j+1$. Nếu tụt về $j=0$ mà vẫn $s[0]\ne s[i]$ thì $\pi [i]=0$.

Hệ quả: $\pi [i]\le \pi [i-1]+1$, hàm tiền tố tăng tối đa $1$ mỗi bước. Đây là chìa khóa của chứng minh độ phức tạp.

Ví dụ chạy tay

Tính hàm tiền tố của aabaaab

Ở mỗi bước, $j$ bắt đầu bằng $\pi [i-1]$; mũi tên ^ chỉ hai ký tự đang so $s[j]$ và $s[i]$.

i=1: j=pi[0]=0.  s[0]='a' vs s[1]='a'  bằng  -> pi[1]=1

i=2: j=pi[1]=1.  s[1]='a' vs s[2]='b'  lệch  -> j=pi[0]=0
                 s[0]='a' vs s[2]='b'  lệch, j=0 -> pi[2]=0

i=3: j=0.        s[0]='a' vs s[3]='a'  bằng  -> pi[3]=1

i=4: j=1.        s[1]='a' vs s[4]='a'  bằng  -> pi[4]=2
       a a b a a
       ^ ^   ^ ^      border "aa" của s[0..4]

i=5: j=2.        s[2]='b' vs s[5]='a'  lệch  -> j=pi[1]=1   (nhảy tới border ngắn hơn)
       a a b a a a
         ^       ^
                 s[1]='a' vs s[5]='a'  bằng  -> pi[5]=2

i=6: j=2.        s[2]='b' vs s[6]='b'  bằng  -> pi[6]=3
       a a b a a a b
       [a a b]     [a a b]   border "aab"

Bước $i=5$ minh họa phép nhảy: border dài nhất của aabaa là aa, nhưng aa + a không phải tiền tố (aab); nhảy xuống border của aa là a, và a + a = aa khớp.

Tìm aba trong abababa

Mẫu $p=$ aba có $\pi =[0,0,1]$. Chạy trực tiếp trên văn bản, $j$ là số ký tự của mẫu đang khớp:

 i    :  0  1  2  3  4  5  6
 t[i] :  a  b  a  b  a  b  a
 j sau:  1  2  3  2  3  2  3
                ^     ^     ^
         khớp đủ ở i=2, 4, 6 -> vị trí bắt đầu 0, 2, 4

Mỗi lần $j=3=m$ ta ghi nhận một lần xuất hiện rồi gán $j\leftarrow \pi [2]=1$ (giữ lại chữ a cuối làm đầu của lần khớp kế tiếp), nhờ vậy bắt được cả các lần xuất hiện chồng lấn.

Cài đặt

C++

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

// pi[i] = length of the longest proper border of s[0..i]
vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                            // longest border of s[0..i-1]
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];  // fall back to next shorter border
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

// All 0-indexed start positions of p in t (no p + '#' + t needed)
vector<int> kmp_search(const string& t, const string& p) {
    vector<int> pi = prefix_function(p), res;
    int m = p.size(), j = 0;                  // j = length of current match
    for (int i = 0; i < (int)t.size(); i++) {
        while (j > 0 && t[i] != p[j]) j = pi[j - 1];
        if (t[i] == p[j]) j++;
        if (j == m) {                         // a full match ends at i
            res.push_back(i - m + 1);
            j = pi[j - 1];                    // continue, overlaps allowed
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t, p;
    cin >> t >> p;
    vector<int> pos = kmp_search(t, p);
    cout << pos.size() << '\n';
    for (int x : pos) cout << x + 1 << ' ';   // print 1-indexed
    cout << '\n';
}

Cách ghép xâu. Có thể thay kmp_search bằng một lần prefix_function(p + '#' + t): vì # không có trong hai xâu nên $\pi$ không bao giờ vượt $m$, và vị trí $i$ (trong xâu ghép) có $\pi [i]=m$ ứng với lần xuất hiện bắt đầu tại $i-2m$ trong $t$. Cách này ngắn nhưng tốn $O(n+m)$ bộ nhớ cho mảng $\pi$ của cả xâu ghép; cách chạy trực tiếp ở trên chỉ cần $O(m)$ và đọc được văn bản theo luồng.

Python

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def kmp_search(t, p):
    pi = prefix_function(p)
    m, j, res = len(p), 0, []
    for i, ch in enumerate(t):
        while j > 0 and ch != p[j]:
            j = pi[j - 1]
        if ch == p[j]:
            j += 1
        if j == m:
            res.append(i - m + 1)
            j = pi[j - 1]
    return res

Với $n$ cỡ ${10}^6$, vòng lặp Python thuần mất khoảng một giây trở lên; nếu chỉ cần có/không hoặc đếm số lần xuất hiện không chồng lấn, str.find/str.count có sẵn nhanh hơn nhiều.

Ứng dụng 1: đếm số lần xuất hiện của mọi tiền tố

Tiền tố độ dài $k$ xuất hiện kết thúc tại $i$ khi và chỉ khi $k$ là độ dài một border của $s[0..i]$ (hoặc $k=i+1$). Mỗi vị trí $i$ góp $1$ cho cả chuỗi $\pi [i],\pi [\pi [i]-1],\dots$. Thay vì đi hết chuỗi cho từng $i$, ta cộng $1$ vào $\pi [i]$ rồi "đẩy" số đếm từ độ dài dài xuống ngắn, giống cộng dồn trên cây:

// cnt[k] = occurrences of the prefix of length k inside s (k >= 1)
vector<long long> count_prefix_occurrences(const string& s) {
    int n = s.size();
    vector<int> pi = prefix_function(s);
    vector<long long> cnt(n + 1, 0);
    for (int i = 0; i < n; i++) cnt[pi[i]]++;             // longest border ending at i
    for (int k = n; k > 0; k--) cnt[pi[k - 1]] += cnt[k];  // push down to shorter borders
    for (int k = 1; k <= n; k++) cnt[k]++;                 // the prefix itself
    return cnt;
}

Vòng thứ hai phải chạy $k$ giảm dần: vì $\pi [k-1]<k$, khi xử lý $k$ thì mọi đóng góp vào cnt[k] từ các độ dài lớn hơn đã được cộng xong. Với ABACABA kết quả là A: 4, AB: 2, ABA: 2, ABAC...ABACABA: 1.

Đếm tiền tố của $s$ trong một xâu khác $t$. Chạy hàm tiền tố trên $s+\mathtt{\text{\#}}+t$ và sửa ba chỗ so với count_prefix_occurrences:

• Vòng đầu chỉ cộng $1$ cho các vị trí thuộc phần $t$.
• Vòng đẩy vẫn chạy $k$ từ $|s|$ xuống $1$, dùng $\pi$ của phần $s$ (các chỉ số $k-1<|s|$ của mảng ghép).
• Bỏ vòng cuối cnt[k]++: "chính tiền tố đó" nằm trong $s$ chứ không nằm trong $t$. Chép nguyên count_prefix_occurrences thì mỗi độ dài bị thừa $1$.

// cnt[k] = occurrences of the prefix of length k of s inside t (k >= 1)
vector<long long> count_prefix_in(const string& s, const string& t) {
    int n = s.size();
    vector<int> pi = prefix_function(s + '#' + t);
    vector<long long> cnt(n + 1, 0);
    for (int i = n + 1; i < (int)pi.size(); i++) cnt[pi[i]]++;  // only positions inside t
    for (int k = n; k > 0; k--) cnt[pi[k - 1]] += cnt[k];      // push down using pi of s only
    return cnt;                                                // no "+1": the prefix lies in s, not t
}

Ứng dụng 2: chu kỳ ngắn nhất và nén xâu

Số $d$ là một chu kỳ của $s$ (độ dài $n$) nếu $s[i]=s[i+d]$ với mọi $i$ hợp lệ. $s$ có chu kỳ $d$ khi và chỉ khi $s$ có border độ dài $n-d$ (dịch xâu đi $d$ ô thì phần chồng lên nhau trùng nhau). Border dài nhất cho chu kỳ ngắn nhất:

$$d_{min}=n-\pi [n-1].$$

Mọi chu kỳ của $s$ là $n-b$ với $b$ chạy trên chuỗi border (kể cả border rỗng $b=0$, cho chu kỳ $n$), nên liệt kê được hết.

Nén thành lũy thừa. $s$ viết được dưới dạng $x^k$ ($x$ lặp $k$ lần, $k\ge 2$) khi và chỉ khi $d_{min}$ chia hết $n$ và $d_{min}<n$; khi đó $x=s[0..d_{min}-1]$ là gốc ngắn nhất. Nếu $d_{min}\nmid n$ thì không có cách chia nào, kể cả với các chu kỳ dài hơn (một chu kỳ $d\mid n$ mà $d<n$ sẽ kéo theo $d_{min}\mid d$ theo định lý Fine-Wilf, nên $d_{min}\mid n$).

 s = a b c a b c a b c     n=9, pi[8]=6, d=3, 9 % 3 == 0 -> (abc)^3
 s = a b c a b c a b       n=8, pi[7]=5, d=3, 8 % 3 != 0 -> không nén được

// length of the shortest x with s = x^k (returns n when s is not a power)
int shortest_root(const string& s) {
    int n = s.size();
    int d = n - prefix_function(s)[n - 1];
    return (n % d == 0) ? d : n;
}

Ứng dụng 3: automaton KMP và DP đếm xâu không chứa mẫu

Trạng thái của KMP khi đọc văn bản chỉ là một số $j\in [0,m]$ (độ dài đang khớp). Ta tính trước bảng chuyển $\text{aut}[j][c]$ = trạng thái mới sau khi đọc ký tự $c$ ở trạng thái $j$, để mỗi bước là $O(1)$ thay vì một vòng while:

• Nếu $j<m$ và $p[j]=c$: $\text{aut}[j][c]=j+1$.
• Ngược lại: $\text{aut}[j][c]=\text{aut}[\pi [j-1]][c]$ (dùng lại hàng của border ngắn hơn, đã tính xong vì $\pi [j-1]<j$), và $\text{aut}[0][c]=0$.

Ví dụ $p=$ aba trên bảng chữ $\{a,b\}$, $\pi =[0,0,1]$:

Đếm xâu độ dài $N$ không chứa $p$. Gọi $f[k][j]$ là số xâu độ dài $k$ mà khi chạy automaton kết thúc ở trạng thái $j<m$ (chưa từng chạm $m$). Chuyển: nếu $\text{aut}[j][c]<m$. Đáp án là ${\sum }_{j}f[N][j]$; số xâu có chứa $p$ bằng $|\Sigma {|}^N$ trừ đi số đó.

Với aba, bắt đầu từ $f[0]=[1,0,0]$:

Kiểm tra: $2^4=16$ xâu, có đúng $4$ xâu chứa aba (abaa, abab, aaba, baba), còn $12$.

const long long MOD = 1e9 + 7;

// aut[j][c] for pattern over 'A'..'Z'; state m means "pattern just matched"
vector<array<int, 26>> build_automaton(const string& p) {
    int m = p.size();
    vector<int> pi = prefix_function(p);
    vector<array<int, 26>> aut(m + 1);
    for (int j = 0; j <= m; j++)
        for (int c = 0; c < 26; c++) {
            if (j < m && p[j] - 'A' == c) aut[j][c] = j + 1;  // extend the match
            else aut[j][c] = (j == 0) ? 0 : aut[pi[j - 1]][c]; // reuse a shorter border's row
        }
    return aut;
}

// number of strings of length N over 'A'..'Z' that contain p, modulo MOD
long long count_containing(int N, const string& p) {
    int m = p.size();
    auto aut = build_automaton(p);
    vector<long long> f(m, 0), g(m);
    f[0] = 1;
    for (int k = 0; k < N; k++) {
        fill(g.begin(), g.end(), 0);
        for (int j = 0; j < m; j++) if (f[j])
            for (int c = 0; c < 26; c++) {
                int to = aut[j][c];
                if (to < m) g[to] = (g[to] + f[j]) % MOD;  // never reach state m
            }
        swap(f, g);
    }
    long long avoid = 0, total = 1;
    for (long long v : f) avoid = (avoid + v) % MOD;
    for (int k = 0; k < N; k++) total = total * 26 % MOD;
    return (total - avoid + MOD) % MOD;
}

Hàng của trạng thái $m$ chỉ dùng khi đếm số lần xuất hiện (văn bản được phép chứa mẫu nhiều lần): sau khi khớp đủ, automaton đi tiếp như từ border $\pi [m-1]$, tương đương dòng j = pi[j - 1] trong kmp_search.

Độ phức tạp

Vì sao hàm tiền tố là $O(n)$ dù có while lồng trong for? Theo dõi biến $j$ (giá trị hiện tại của $\pi$):

• Mỗi bước for, $j$ tăng nhiều nhất $1$ (dòng j++). Qua cả thuật toán, tổng mức tăng $\le n-1$.
• Mỗi lần lặp while, $j$ giảm ít nhất $1$ (vì $\pi [j-1]<j$), và $j$ không bao giờ âm.

Tổng mức giảm không thể vượt tổng mức tăng, nên tổng số lần lặp while qua toàn bộ thuật toán $\le n-1$. Cộng với $n$ bước for được $O(n)$. Lập luận khấu hao y hệt cho kmp_search: $j$ tăng tối đa $n$ lần (một lần mỗi ký tự văn bản), nên phần while tổng cộng $O(n)$, cộng $O(m)$ tính $\pi$ của mẫu.

Chú ý đây là cận tổng: một bước đơn lẻ vẫn có thể lặp while tới $O(m)$ lần. Khi cần đảm bảo mỗi ký tự xử lý trong $O(1)$ (chẳng hạn trong DP phải xử lý từng trạng thái riêng lẻ, nơi lập luận khấu hao không còn đúng), hãy dùng automaton.

So sánh với Z-function và hash

Quy tắc chọn nhanh: cần trạng thái khớp (DP, automaton, xóa mẫu khi đang đọc) thì dùng KMP; cần "đoạn bắt đầu tại $i$ khớp tiền tố dài bao nhiêu" thì Z-function tự nhiên hơn; cần so sánh đoạn con tùy ý hoặc kết hợp chặt nhị phân thì dùng hash.

⚠️ Lỗi thường gặp

• Dùng if thay cho while khi lùi. Chỉ lùi một bước j = pi[j-1] rồi thôi sẽ bỏ sót các border ngắn hơn. Với aabaaab lỗi này không lộ ra (mỗi bước chỉ cần lùi một lần), nhưng với aaab bước cuối phải lùi $2\to 1\to 0$: bản dùng if cho $\pi =[0,1,2,1]$ thay vì đúng là $[0,1,2,0]$. Luôn lùi cho tới khi khớp hoặc $j=0$.
• Không gán lại $j$ sau khi khớp đủ, hoặc gán sai. Trong kmp_search, nếu để nguyên $j=m$ thì bước sau đọc p[m]: với vector<int> hay mảng số đó là truy cập ra ngoài mảng. Với std::string, p[m] trả về '\0' (hành vi được chuẩn định nghĩa từ C++11) nên code vẫn chạy đúng khi $t$ không chứa '\0', nhưng đó chỉ là nhờ ký tự '\0' ở cuối, không nên dựa vào. Nếu gán j = 0 thì bỏ sót các lần xuất hiện chồng lấn: tìm aa trong aaaa được $2$ thay vì $3$. Gán đúng là j = pi[m-1].
• Ký tự ngăn cách có trong dữ liệu. Khi ghép $p+\mathtt{\text{\#}}+t$, nếu # (hoặc ký tự nào đó bạn chọn) có thể xuất hiện trong $t$ hay $p$ thì $\pi$ có thể vượt $m$ và đếm sai. Với dữ liệu là dãy số, ghép bằng một giá trị chắc chắn không có (ví dụ $-1$) thay vì ký tự.
• Lệch chỉ số khi ghép. Trong $p+\mathtt{\text{\#}}+t$, vị trí $i$ có $\pi [i]=m$ ứng với vị trí bắt đầu $i-2m$ trong $t$ (chỉ số từ $0$), không phải $i-m$. Đề đánh số từ $1$ thì cộng $1$.
• Tưởng $n-\pi [n-1]$ luôn nén được xâu. Đó là chu kỳ ngắn nhất, nhưng chỉ nén thành $x^k$ khi nó chia hết $n$. abcab có chu kỳ $3$ nhưng không là lũy thừa của xâu nào ngắn hơn. Ngược lại, đừng thử các chu kỳ dài hơn khi $d_{min}\nmid n$: không cái nào chia hết $n$.
• Cộng dồn số lần xuất hiện sai chiều. Trong count_prefix_occurrences, vòng đẩy cnt[pi[k-1]] += cnt[k] phải chạy $k$ giảm dần. Chạy tăng dần thì cnt[k] được đẩy xuống trước khi nhận đủ đóng góp từ các độ dài lớn hơn.
• Tưởng KMP luôn là $O(1)$ mỗi ký tự. Cận $O(n)$ là khấu hao. Nếu DP gọi hàm "chuyển trạng thái bằng while" từ mọi trạng thái ở mọi bước, không còn tính khấu hao, chi phí có thể thành $O(N·m^2·|\Sigma |)$. Tính trước bảng aut rồi mới DP.
• Quên modulo hoặc tràn số khi đếm. $|\Sigma {|}^N$ và các giá trị $f$ tăng rất nhanh; lấy modulo ở mỗi phép cộng và cộng thêm MOD trước khi lấy phần dư của hiệu $|\Sigma {|}^N-\text{avoid}$.

Biến thể / Mở rộng

• Nhiều mẫu cùng lúc. Dựng trie của các mẫu và thay $\pi$ bằng liên kết hậu tố (suffix link): đó chính là Aho-Corasick, "KMP trên cây". Bảng chuyển aut ở trên là trường hợp trie chỉ có một nhánh; DP đếm xâu không chứa bất kỳ mẫu nào hoạt động y hệt trên automaton Aho-Corasick.
• $N$ rất lớn. Chuyển trạng thái $f[k]\to f[k+1]$ là tuyến tính và không phụ thuộc $k$, nên viết thành ma trận $m\times m$ và lũy thừa trong $O(m^3\log N)$, xem DP nhân ma trận và lũy thừa ma trận.
• Trạng thái KMP làm một chiều của DP. Bài "xóa ít ký tự nhất để $s$ không chứa $p$", "dựng xâu chứa $p$ nhiều lần nhất"... đều là DP với trạng thái (vị trí trong $s$, trạng thái automaton). Tương tự DP chữ số khi yêu cầu "số không chứa dãy chữ số cho trước".
• Xóa mẫu khi đang đọc. Dùng một ngăn xếp các ký tự còn lại và lưu trạng thái KMP tại mỗi ký tự; khi khớp đủ $m$ thì bỏ $m$ phần tử đỉnh và khôi phục trạng thái của phần tử mới ở đỉnh. Tổng $O(n+m)$ dù mỗi lần xóa có thể tạo ra lần xuất hiện mới.
• Xoay vòng và dãy số. $b$ là một phép xoay của $a$ khi và chỉ khi $|a|=|b|$ và $b$ xuất hiện trong $a+a$. Thiếu điều kiện cùng độ dài thì mọi xâu con ngắn hơn của $a+a$ cũng bị nhận nhầm là phép xoay. KMP chạy được trên mảng số bất kỳ có phép so sánh bằng, ví dụ so khớp "hình dạng" của dãy bằng cách tìm trên dãy hiệu $a_{i+1}-a_i$.
• Hàm tiền tố và Z-function chuyển đổi được cho nhau trong $O(n)$, nên bài nào giải được bằng cái này thì về lý thuyết cũng giải được bằng cái kia; chọn cái cho code gọn nhất. Các cấu trúc mạnh hơn cho câu hỏi về mọi đoạn con: suffix array, suffix automaton.

Bài tập luyện

Luyện kỹ thuật

• Kiểm duyệt (Silver) (censorsi) (Trung cấp) xóa lặp đi lặp lại lần xuất hiện sớm nhất của mẫu: dùng ngăn xếp ký tự kèm trạng thái KMP để xóa ngay khi khớp đủ, không phải quét lại từ đầu.
• Khớp Xâu (strmatch) (Trung cấp) đếm số lần xuất hiện (kể cả chồng lấn) của mẫu trong xâu dài tới ${10}^6$: cài đặt trực tiếp kmp_search.
• Tìm Chu Kỳ (periods) (Nâng cao) liệt kê mọi chu kỳ: đi theo chuỗi border $\pi [n-1],\pi [\pi [n-1]-1],\dots$, mỗi border $b$ cho chu kỳ $n-b$, kể cả $b=0$ cho chu kỳ $n$.
• Xâu Con Bắt Buộc (reqsubstr) (Kỳ cựu) đếm xâu độ dài $n$ chứa mẫu: DP trên automaton KMP đếm phần bù, đúng như count_containing ở trên.
• Tiền tố trùng Hậu tố (borderocc) (Kỳ cựu) liệt kê border của cả xâu và số lần xuất hiện của từng border: kết hợp chuỗi border với count_prefix_occurrences.

Muốn luyện thêm: Xóa Ký Tự Trong Chuỗi (necklace) (Kỳ cựu) là DP tối ưu (xóa ít ký tự nhất) với trạng thái automaton KMP thay vì DP đếm.

Đề VOI

Bài VOI 2005 dưới đây dùng automaton KMP như một thành phần của lời giải chính. Hai bài còn lại chỉ có một phần giải được gọn bằng hàm tiền tố, nhưng đó chỉ là một cách làm, không phải hướng chính thức:

• Pháo hoa (voi05_firewk) (Chuyên gia) VOI 2005: một bước của lời giải là DP trên automaton KMP của mã cho trước để đếm các từ vòng tránh một tập mẫu, tương tự count_containing ở trên nhưng chạy trên vòng.
• Bản vanxơ Fibonacci (voi12_fibval) (Nâng cao) VOI 2012: lời giải chính dựa vào tính tuần hoàn của dãy Fibonacci. Với các đoạn ngắn cần kiểm tra trực tiếp "đoạn có chia được thành $k\ge 2$ khối giống nhau không": với mỗi điểm bắt đầu, tính hàm tiền tố của đoạn phía sau rồi dùng điều kiện chu kỳ ngắn nhất chia hết độ dài, thay cho việc thử mọi ước.
• Virus (voi17_virus) (Nâng cao) VOI 2017: lời giải chính thức là cửa sổ trượt trên mảng sai khác. Riêng subtask $k=0$ (tìm đoạn dạng $XX$ dài nhất), có thể chạy hàm tiền tố từ mỗi điểm bắt đầu và nhận ra một đoạn độ dài $2L$ có dạng $XX$ khi và chỉ khi chu kỳ ngắn nhất của nó chia hết $L$.