理論與進階主題
字串比對
字串比對要解決的是：在一段較長的文本裡，找出一個較短的模式串出現在何處——這正是你按下 Ctrl-F 在文件裡查找時發生的事。我們把文本長度記為 n，模式串長度記為 m。最老實、最直白的辦法是樸素演算法：把模式對齊到文本的第一個位置，逐字元比較；若相符則回報，若不符就把模式向右滑一格再試。簡單而正確。
麻煩在它的最壞情形。大約 n 個起始位置中，每一個都可能在出現不符前比較多達 m 次，因此樸素法的代價是 O(nm)——而像在一長串「aaaaaaaa…」中查找「aaaab」這類刁鑽輸入，確實會觸到這個上界。浪費之處在於：一次部分相符失敗後，樸素法把剛學到的一切統統丟棄，讓模式從頭重來，把已經看過的文本字元又看一遍。
Knuth-Morris-Pratt 演算法（KMP）正好修掉這份浪費，達到 O(n + m)。它的關鍵洞見是：當不符發生在模式中途時，已經相符的那些字元本就是模式自身的一部分，因此我們往往已經知道模式的某個前綴仍然對得上——根本不必重新檢查它。KMP 預先算出一張小小的「前綴表」（又稱失配函式），對模式中的每個位置，記錄在此結束的、既是前綴又是後綴的最長長度。建表代價 O(m)；隨後文本只被掃一遍、絕不回退，代價 O(n)。它的思路是「記住，而非重掃」——這就把一次乘法變成了一次加法。
// naive O(n*m): re-checks text it has already seen
std::vector<int> findAll(const std::string& text,
const std::string& pat) {
std::vector<int> hits;
int n = text.size(), m = pat.size();
for (int i = 0; i + m <= n; ++i) { // each start position
int j = 0;
while (j < m && text[i + j] == pat[j]) ++j; // up to m compares
if (j == m) hits.push_back(i); // full match at i
}
return hits; // KMP avoids the restarts
}樸素比對是 O(nm)；KMP 的前綴表把它降到 O(n + m)。
KMP 的前綴表（失配函式）就是全部訣竅：它告訴搜尋在不符後能安全地把模式跳多遠，從而絕不重掃文本。
又稱
另見