字串獵人 - KMP Algorithm ← 返回遊戲列表
Text:
Pattern:
0
比較次數
0
找到匹配
0
當前位置

Prefix Function π[]

匹配
失配
比較中

KMP 演算法

核心思想:利用已匹配的資訊,失配時不從頭開始。

Prefix Function π[i]:Pattern[0..i] 的最長「前綴 = 後綴」長度
例如 ABABC:π = [0, 0, 1, 2, 0]

失配時:Pattern 移到 π[j-1] 位置繼續比較,而非從頭開始
時間複雜度O(n + m),其中 n = text 長度,m = pattern 長度