bm[BM匹配算法]

BM算法被認為是亞線性串匹配算法，它在最壞情況下找到模式所有出現的時間複雜度為O(mn)，在最好情況下執行匹配找到模式所有出現的時間複雜度為O(n/m)。

基本信息

• 英文名：bm
• 其他外文名：Boyer-Moore

• 含義：一種精確字元串匹配算法
• 套用領域：Boyer-Moore

BM算法主要思想描述如下

(1)模式字元串的匹配順序是從右向左:

(a)首先將P和T對齊,即p[0]和t[0]對齊；

(b)然後匹配從模式字元串P的最右端字元開始，即判斷

p[m]和t[m]是否匹配：

如果匹配成功,則向左移動判斷

p[m-1]和t[m-1]是否匹配，如此循環下去；如果匹配不成功，則進行字元串滑移。

(2)字元串滑移啟發式策略：

(a)壞字元移動啟發式策略

(b)好後綴移動啟發式策略

兩種策略的使用：如果同時滿足兩種策略使用條件時，選兩者中較大的作為模式串向右滑移的距離。