在數據結構的學習路徑上,字符串(也稱「串」)常被視為一種特殊的線性表。本文是這個系列的第四篇,重點放在串的抽象定義,以及最直觀易懂的模式匹配算法——BF(Brute Force,暴力匹配,又稱樸素匹配或蠻力算法)。
串是由零個或多個字符組成的有限序列。它的邏輯結構與線性表高度相似:元素按先後順序排成一條線,每個位置對應唯一元素。真正的差別在於操作對象——串的元素被限定為字符,因此圍繞它展開的操作也完全不同。
線性表更關注單個元素的增刪改查(CRUD),串則更關注定位與替換:某個子串第一次出現在哪裡、如何把一段內容替換掉、如何截取片段。各高級語言對串的基本操作命名不同,但本質相通。以 JavaScript 為例,查找用 indexOf,去空白用 trim,大小寫轉換用 toLowerCase / toUpperCase。
字符串匹配有三個繞不開的名字:BF、BM、KMP。它們解決的是同一個問題——在主串中找出模式串第一次出現的位置——差別在於「失配之後怎麼走」。
從主串 s 的第一個字符開始,與模式串 t 的第一個字符比較。若相等,就繼續逐個向後比較;若不相等,主串指針回到起點的下一個位置,模式串指針回到首位,重新開始比較。
如此反覆,直到模式串 t 的每個字符都與主串 s 中某段連續字符依次相等,則匹配成功,此時 t 的首字符在 s 中的下標即為結果;若一直走到主串末尾仍未成功,則匹配失敗。

可以看到,BF 的思路非常「樸素」:主串的每個位置都試一次,試到為止。它的實現恰好對應了 JavaScript 中 indexOf 的內涵。
以主串 BBC ABB ABCF、子串 ABC 為例:
var sourceStr = "BBC ABB ABCF";
var searchStr = "ABC";
function BF_Ordinary(sourceStr, searchStr) {
var sourceLength = sourceStr.length;
var searchLength = searchStr.length;
var padding = sourceLength - searchLength;
// 外層最多只需要比較 padding + 1 次
for (var i = 0; i <= padding; i++) {
// 首字符相等才進入內層逐位比對
if (sourceStr.charAt(i) == searchStr.charAt(0)) {
var complete = searchLength;
for (var j = 0; j < searchLength; j++) {
if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {
--complete;
if (!complete) return i; // 全部匹配完成
}
}
}
}
return -1;
}
這段代碼有三個容易寫錯的地方:
sourceLength - searchLength,因為主串剩餘長度小於子串時不可能再匹配成功,繼續循環是浪費。i + j,而不是單獨用 j。complete 判斷是否全部匹配。在 BBC ABB ABCF 的例子中,第二段的 ABB 首字符相同但後續不同,必須能被正確跳過。與其統計「匹配了多少個」,不如只關注「有沒有不匹配」。一旦發現某一位不同,立刻判定本輪失敗並跳出內層。
function BF_Optimize(sourceStr, searchStr) {
var mainLength = sourceStr.length;
var searchLength = searchStr.length;
var padding = mainLength - searchLength;
for (var offset = 0; offset <= padding; offset++) {
var match = true;
for (var i = 0; i < searchLength; i++) {
// 只要出現一次不相等就結束本輪
if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
match = false;
break;
}
}
if (match) return offset;
}
return -1;
}
內層循環完整跑完而 match 未被改寫,即說明這一輪是完全匹配。這種「取反短路」的寫法通常比正統計數更易讀,也更符合多數語言的習慣。
仔細觀察會發現規律:外層每次只把主串起點後移一位,內層每次都從模式串頭部重新開始。既然如此,其實可以只用一個 while 循環,靠兩個下標指針的移動來表達同樣的過程。
function BF_Optimize_2(sourceStr, searchStr) {
var i = 0, j = 0;
while (i < sourceStr.length) {
if (sourceStr.charAt(i) == searchStr.charAt(j)) {
i++; j++; // 相等則同時前進
} else {
i = i - j + 1; // 主串回到本輪起點的下一個位置
j = 0; // 模式串回到首位
}
if (j == searchStr.length) {
return i - j; // 模式串走完,i - j 即起始下標
}
}
return -1;
}
這裡的關鍵是回退公式 i = i - j + 1。因為在內層推進過程中 i 已經被疊加了 j 次,要退回「本輪起點 + 1」,就必須先減去 j 再加一。很多實現出錯都出在這一步。
function BF_Recursive(sourceStr, searchStr, offset) {
var mainLength = sourceStr.length;
var searchLength = searchStr.length;
// 剩餘長度不足以容納模式串,直接失敗
if (searchLength > mainLength - offset) return -1;
offset = offset || 0;
for (var i = 0; i < searchLength; i++) {
if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
return BF_Recursive(sourceStr, searchStr, offset + 1);
}
}
return offset;
}
遞歸版本的語義最貼近算法定義本身:當前位置不匹配,就把起點右移一位再問一次自己。代價是額外的函數調用開銷,在字符串很長時需要留意棧深度。
BF 的最壞時間複雜度為 O(mn)(m 為模式串長度,n 為主串長度),空間複雜度 O(1)。它的致命弱點在於:一旦某一位失配,主串指針必須整體回退,此前已經比較過的字符信息全部被丟棄、重新比較。
當主串中存在大量重複前綴(例如 aaaaaaaab 中查找 aaab)時,這種浪費會被放大得非常明顯。BF 屬於前綴匹配算法,如何「不回退地利用已匹配信息」,正是 KMP 與 BM 要解決的問題,後續文章會接著展開。