在電腦裡「找一個字」其實無所不在:文字編輯器按 Ctrl+F、瀏覽器搜尋頁面關鍵字,骨子裡都是同一件事——在一長串文字裡找出某個短字串出現在哪。 最直覺的做法是把短字串貼上去、從頭一位一位比對,可是只要中途對不上就得整個退回、往右挪一格重來,碰到「很像卻差一點」時會白忙好多次。 於是有人想:能不能記住剛剛已經比對過的資訊,對不上時少退幾步?這就是 KMP、Z-Function 這些聰明做法在做的事。 下面你會看到暴力法和幾種進階方法並排跑同一組文字,比比看各花了多少次比對。
這頁比較幾種「在一大段文字裡找出某個關鍵字出現在哪」的方法。暴力法逐位對,簡單但每次對不上就得從頭退回來; KMP 先分析關鍵字自身的重複結構,對不上時能少退一點、不整個從頭來;Rabin-Karp 改用「數字指紋」快速比對整段; Z-Function 則預先算出關鍵字各位置的匹配資訊。你可以看到同樣找一個字,各方法的比對次數差多少,體會「多花一點預處理、換之後找得更快」。