核心思想:利用已匹配的資訊,失配時不從頭開始。 Prefix Function π[i]:Pattern[0..i] 的最長「前綴 = 後綴」長度 例如 ABABC:π = [0, 0, 1, 2, 0] 失配時:Pattern 移到 π[j-1] 位置繼續比較,而非從頭開始 時間複雜度:O(n + m),其中 n = text 長度,m = pattern 長度
ABABC
O(n + m)