Boyer–Moore 算法
前置知识:前缀函数与 KMP 算法。
KMP 算法将前缀匹配的信息用到了极致,
而 BM 算法背后的基本思想是通过后缀匹配获得比前缀匹配更多的信息来实现更快的字符跳转。
引入
想象一下,如果我们的的模式字符串 𝑝𝑎𝑡
,被放在文本字符串 𝑠𝑡𝑟𝑖𝑛𝑔
的左手起头部,使它们的第一个字符对齐。
𝑝𝑎𝑡:𝙴𝚇𝙰𝙼𝙿𝙻𝙴𝑠𝑡𝑟𝑖𝑛𝑔:𝙷𝙴𝚁𝙴 𝙸𝚂 𝙰 𝚂𝙸𝙼𝙿𝙻𝙴 𝙴𝚇𝙰𝙼𝙿𝙻𝙴… ⇑
在这里做定义,往后不赘述:
𝑝𝑎𝑡
的长度为 𝑝𝑎𝑡𝑙𝑒𝑛
,特别地对于从 0 开始的串来说,规定 𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 =𝑝𝑎𝑡𝑙𝑒𝑛 −1
为 𝑝𝑎𝑡
串最后一个字符的位置;
𝑠𝑡𝑟𝑖𝑛𝑔
的长度 𝑠𝑡𝑟𝑖𝑛𝑔𝑙𝑒𝑛
,𝑠𝑡𝑟𝑖𝑛𝑔𝑙𝑎𝑠𝑡𝑝𝑜𝑠 =𝑠𝑡𝑟𝑖𝑛𝑔𝑙𝑒𝑛 −1
。
假如我们知道了 𝑠𝑡𝑟𝑖𝑛𝑔
的第 𝑝𝑎𝑡𝑙𝑒𝑛
个字符 𝑐ℎ𝑎𝑟
(与 𝑝𝑎𝑡
的最后一个字符对齐)考虑我们能得到什么信息:
观察 1
如果我们知道 𝑐ℎ𝑎𝑟
这个字符不在 𝑝𝑎𝑡
中,我们就不用考虑 𝑝𝑎𝑡
从 𝑠𝑡𝑟𝑖𝑛𝑔
的第 1
个、第 2
个……第 𝑝𝑎𝑡𝑙𝑒𝑛
个字符起出现的情况,,而可以直接将 𝑝𝑎𝑡
向下滑动 𝑝𝑎𝑡𝑙𝑒𝑛
个字符。
观察 2
更一般地,如果出现在 𝑝𝑎𝑡
最末尾(也就是最右边)的那一个 𝑐ℎ𝑎𝑟
字符的位置是离末尾端差了 𝑑𝑒𝑙𝑡𝑎1
个字符,
那么就可以不用匹配,直接将 𝑝𝑎𝑡
向后滑动 𝑑𝑒𝑙𝑡𝑎1
个字符:如果滑动距离少于 𝑑𝑒𝑙𝑡𝑎1
,那么仅就 𝑐ℎ𝑎𝑟
这个字符就无法被匹配,当然模式字符串 𝑝𝑎𝑡
也就不会被匹配。
因此除非 𝑐ℎ𝑎𝑟
字符可以和 𝑝𝑎𝑡
末尾的那个字符匹配,否则 𝑠𝑡𝑟𝑖𝑛𝑔
要跳过 𝑑𝑒𝑙𝑡𝑎1
个字符(相当于 𝑝𝑎𝑡
向后滑动了 𝑑𝑒𝑙𝑡𝑎1
个字符)。并且我们可以得到一个计算 𝑑𝑒𝑙𝑡𝑎1
的函数 𝑑𝑒𝑙𝑡𝑎1(𝑐ℎ𝑎𝑟)
:
𝐢𝐧𝐭 𝑑𝑒𝑙𝑡𝑎1(𝐜𝐡𝐚𝐫 𝑐ℎ𝑎𝑟)𝐢𝐟 char不在pat中 || char是pat上最后一个字符𝐫𝐞𝐭𝐮𝐫𝐧 𝑝𝑎𝑡𝑙𝑒𝑛𝐞𝐥𝐬𝐞𝐫𝐞𝐭𝐮𝐫𝐧 𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠−𝑖// i为出现在pat最末尾的那一个char出现的位置,即pat[i]=char
需要注意,显然这个表只需计算到 𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −1
的位置。
现在假设 𝑐ℎ𝑎𝑟
和 𝑝𝑎𝑡
最后一个字符匹配到了,那我们就看看 𝑐ℎ𝑎𝑟
前一个字符和 𝑝𝑎𝑡
的倒数第二个字符是否匹配:
如果是,就继续回退直到整个模式串 𝑝𝑎𝑡
完成匹配(这时我们就在 𝑠𝑡𝑟𝑖𝑛𝑔
上成功得到了一个 𝑝𝑎𝑡
的匹配);
或者,我们也可能会在匹配完 𝑝𝑎𝑡
的倒数第 𝑚
个字符后,在倒数第 𝑚 +1
个字符上失配,这时我们就希望把 𝑝𝑎𝑡
向后滑动到下一个可能会实现匹配的位置,当然我们希望滑动得越远越好。
观察 3(a)
在 观察 2 中提到,当匹配完 𝑝𝑎𝑡
的倒数 𝑚
个字符后,如果在倒数第 𝑚 +1
个字符失配,为了使得 𝑠𝑡𝑟𝑖𝑛𝑔
中的失配字符与 𝑝𝑎𝑡
上对应字符对齐,
需要把 𝑝𝑎𝑡
向后滑动 𝑘
个字符,也就是说我们应该把注意力看向之后的 𝑘 +𝑚
个字符(也就是看向 𝑝𝑎𝑡
滑动 k 之后,末段与 𝑠𝑡𝑟𝑖𝑛𝑔
对齐的那个字符)。
而 𝑘 =𝑑𝑒𝑙𝑡𝑎1 −𝑚
,
所以我们的注意力应该沿着 𝑠𝑡𝑟𝑖𝑛𝑔
向后跳 𝑑𝑒𝑙𝑡𝑎1 −𝑚 +𝑚 =𝑑𝑒𝑙𝑡𝑎1
个字符。
然而,我们有机会跳过更多的字符,请继续看下去。
观察 3(b)
如果我们知道 𝑠𝑡𝑟𝑖𝑛𝑔
接下来的 𝑚
个字符和 𝑝𝑎𝑡
的最后 𝑚
个字符匹配,假设这个子串为 𝑠𝑢𝑏𝑝𝑎𝑡
,
我们还知道在 𝑠𝑡𝑟𝑖𝑛𝑔
失配字符 𝑐ℎ𝑎𝑟
后面是与 𝑠𝑢𝑏𝑝𝑎𝑡
相匹配的子串,而假如 𝑝𝑎𝑡
对应失配字符前面存在 𝑠𝑢𝑏𝑝𝑎𝑡
,我们可以将 𝑝𝑎𝑡
向下滑动一段距离,
使得失配字符 𝑐ℎ𝑎𝑟
在 𝑝𝑎𝑡
上对应的字符前面出现的 𝑠𝑢𝑏𝑝𝑎𝑡
(合理重现,plausible reoccurrence,以下也简称 pr)与 𝑠𝑡𝑟𝑖𝑛𝑔
的 𝑠𝑢𝑏𝑝𝑎𝑡
对齐。如果 𝑝𝑎𝑡
上有多个 𝑠𝑢𝑏𝑝𝑎𝑡
,按照从右到左的后缀匹配顺序,取第一个(rightmost plausible reoccurrence,以下也简称 rpr)。
假设此时 𝑝𝑎𝑡
向下滑动的 𝑘
个字符(也即 𝑝𝑎𝑡
末尾端的 𝑠𝑢𝑏𝑝𝑎𝑡
与其最右边的合理重现的距离),这样我们的注意力应该沿着 𝑠𝑡𝑟𝑖𝑛𝑔
向后滑动 𝑘 +𝑚
个字符,这段距离我们称之为 𝑑𝑒𝑙𝑡𝑎2(𝑗)
:
假定 𝑟𝑝𝑟(𝑗)
为 𝑠𝑢𝑏𝑝𝑎𝑡 =𝑝𝑎𝑡[𝑗 +1…𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠]
在 𝑝𝑎𝑡[𝑗]
上失配时的最右边合理重现的位置,𝑟𝑝𝑟(𝑗) <𝑗
(这里只给出简单定义,在下文的算法设计章节里会有更精确的讨论),那么显然 𝑘 =𝑗 −𝑟𝑝𝑟(𝑗), 𝑚 =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −𝑗
。
所以有:
𝐢𝐧𝐭 𝑑𝑒𝑙𝑡𝑎2(𝐢𝐧𝐭 𝑗)// j为失配字符在pat上对应字符的位置𝐫𝐞𝐭𝐮𝐫𝐧 𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠−𝑟𝑝𝑟(𝑗)
于是我们在失配时,可以把把 𝑠𝑡𝑟𝑖𝑛𝑔
上的注意力往后跳过 max(𝑑𝑒𝑙𝑡𝑎1,𝑑𝑒𝑙𝑡𝑎2)
个字符
过程
箭头指向失配字符 𝑐ℎ𝑎𝑟
:
𝑝𝑎𝑡:𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
𝙵
没有出现 𝑝𝑎𝑡
中,根据 观察 1,𝑝𝑎𝑡
直接向下移动 𝑝𝑎𝑡𝑙𝑒𝑛
个字符,也就是 7 个字符:
𝑝𝑎𝑡: 𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
根据 观察 2,我们需要将 𝑝𝑎𝑡
向下移动 4 个字符使得短横线字符对齐:
𝑝𝑎𝑡: 𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
现在char:𝚃
匹配了,把 𝑠𝑡𝑟𝑖𝑛𝑔
上的指针左移一步继续匹配:
𝑝𝑎𝑡: 𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
根据 观察 3(a),𝙻
失配,因为 𝙻
不在 𝑝𝑎𝑡
中,所以 𝑝𝑎𝑡
向下移动 𝑘 =𝑑𝑒𝑙𝑡𝑎1 −𝑚 =7 −1 =6
个字符,而 𝑠𝑡𝑟𝑖𝑛𝑔
上指针向下移动 𝑑𝑒𝑙𝑡𝑎1 =7
个字符:
𝑝𝑎𝑡: 𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
这时 𝑐ℎ𝑎𝑟
又一次匹配到了 𝑝𝑎𝑡
的最后一个字符 𝚃
,𝑠𝑡𝑟𝑖𝑛𝑔
上的指针向左匹配,匹配到了 𝙰
,继续向左匹配,发现在字符 -
失配:
𝑝𝑎𝑡: 𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
显然直观上看,此时根据 观察 3(b),将 𝑝𝑎𝑡
向下移动 𝑘 =5
个字符,使得后缀 𝙰𝚃
对齐,这种滑动可以获得 𝑠𝑡𝑟𝑖𝑛𝑔
指针最大的滑动距离,此时 𝑑𝑒𝑙𝑡𝑎2 =𝑘 +𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −𝑗 =5 +6 −4 =7
,即 𝑠𝑡𝑟𝑖𝑛𝑔
上指针向下滑动 7 个字符。
而从形式化逻辑看,此时,𝑑𝑒𝑙𝑡𝑎1 =7 −1 −2 =4, 𝑑𝑒𝑙𝑡𝑎2 =7,max(𝑑𝑒𝑙𝑡𝑎1,𝑑𝑒𝑙𝑡𝑎2) =7
,
这样从形式逻辑上支持了进行 观察 3(b) 的跳转:
𝑝𝑎𝑡:𝙰𝚃-𝚃𝙷𝙰𝚃𝑠𝑡𝑟𝑖𝑛𝑔: … 𝚆𝙷𝙸𝙲𝙷-𝙵𝙸𝙽𝙰𝙻𝙻𝚈-𝙷𝙰𝙻𝚃𝚂.--𝙰𝚃-𝚃𝙷𝙰𝚃-𝙿𝙾𝙸𝙽𝚃… ⇑
现在我们发现了 𝑝𝑎𝑡
上每一个字符都和 𝑠𝑡𝑟𝑖𝑛𝑔
上对应的字符相等,我们在 𝑠𝑡𝑟𝑖𝑛𝑔
上找到了一个 𝑝𝑎𝑡
的匹配。而只花费了 14 次对 𝑠𝑡𝑟𝑖𝑛𝑔
的引用,其中 7 次是完成一个成功的匹配所必需的比较次数(𝑝𝑎𝑡𝑙𝑒𝑛 =7
),另外 7 次让我们跳过了 22 个字符。
算法设计
最初的匹配算法
解释
现在看这样一个利用 𝑑𝑒𝑙𝑡𝑎1
和 𝑑𝑒𝑙𝑡𝑎2
进行字符串匹配的算法:
𝑖←𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠.𝑗←𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠.𝐥𝐨𝐨𝐩𝐢𝐟 𝑗<0𝐫𝐞𝐭𝐮𝐫𝐧 𝑖+1𝐢𝐟 𝑠𝑡𝑟𝑖𝑛𝑔[𝑖]=𝑝𝑎𝑡[𝑗]𝑗←𝑗−1𝑖←𝑖−1𝐜𝐨𝐧𝐭𝐢𝐧𝐮𝐞𝑖←𝑖+𝑚𝑎𝑥(𝑑𝑒𝑙𝑡𝑎1(𝑠𝑡𝑟𝑖𝑛𝑔[𝑖]),𝑑𝑒𝑙𝑡𝑎2(𝑗))𝐢𝐟 𝑖>𝑠𝑡𝑟𝑖𝑛𝑔𝑙𝑎𝑠𝑡𝑝𝑜𝑠𝐫𝐞𝐭𝐮𝐫𝐧 𝑓𝑎𝑙𝑠𝑒𝑗←𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠
如果上面的算法 𝐫𝐞𝐭𝐮𝐫𝐧 𝑓𝑎𝑙𝑠𝑒
,表明 𝑝𝑎𝑡
不在 𝑠𝑡𝑟𝑖𝑛𝑔
中;如果返回一个数字,表示 𝑝𝑎𝑡
在 𝑠𝑡𝑟𝑖𝑛𝑔
左起第一次出现的位置。
然后让我们更精细地描述下计算 𝑑𝑒𝑙𝑡𝑎2
,所依靠的 𝑟𝑝𝑟(𝑗)
函数。
根据前文定义,𝑟𝑝𝑟(𝑗)
表示在 𝑝𝑎𝑡(𝑗)
失配时,子串 𝑠𝑢𝑏𝑝𝑎𝑡 =𝑝𝑎𝑡[𝑗 +1…𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠]
在 𝑝𝑎𝑡[𝑗]
最右边合理重现的位置。
也就是说需要找到一个最好的 𝑘
, 使得 𝑝𝑎𝑡[𝑘…𝑘 +𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −𝑗 −1] =𝑝𝑎𝑡[𝑗 +1…𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠]
,另外要考虑两种特殊情况:
- 当 𝑘 <0
时,相当于在 𝑝𝑎𝑡
前面补充了一段虚拟的前缀,实际上也符合 𝑑𝑒𝑙𝑡𝑎2
跳转的原理。
- 当 𝑘 >0
时,如果 𝑝𝑎𝑡[𝑘 −1] =𝑝𝑎𝑡[𝑗]
,则这个 𝑝𝑎𝑡[𝑘…𝑘 +𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −𝑗 −1]
不能作为 𝑠𝑢𝑏𝑝𝑎𝑡
的合理重现。
原因是 𝑝𝑎𝑡[𝑗]
本身是失配字符,所以 𝑝𝑎𝑡
向下滑动 𝑘
个字符后,在后缀匹配过程中仍然会在 𝑝𝑎𝑡[𝑘 −1]
处失配。
还要注意两个限制条件:
- 𝑘 <𝑗
。因为当 𝑘 =𝑗
时,有 𝑝𝑎𝑡[𝑘] =𝑝𝑎𝑡[𝑗]
,在 𝑝𝑎𝑡[𝑗]
上失配的字符也会在 𝑝𝑎𝑡[𝑘]
上失配。
- 考虑到 𝑑𝑒𝑙𝑡𝑎2(𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠) =0
,所以规定 𝑟𝑝𝑟(𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠) =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠
。
过程
由于理解 𝑟𝑝𝑟(𝑗)
是实现 BoyerMoore 算法的核心,所以我们使用如下两个例子进行详细说明:
𝑗: 𝟶 𝟷 𝟸 𝟹 𝟺 𝟻 𝟼 𝟽 𝟾𝑝𝑎𝑡: 𝙰 𝙱 𝙲 𝚇 𝚇 𝚇 𝙰 𝙱 𝙲𝑟𝑝𝑟(𝑗): 𝟻 𝟺 𝟹 𝟸 𝟷 𝟶 𝟸 𝟷 𝟾𝑠𝑔𝑛: - - - - - - - - +
对于 𝑟𝑝𝑟(0)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙱𝙲𝚇𝚇𝚇𝙰𝙱𝙲
,在 𝑝𝑎𝑡[0]
之前的最右边合理重现只能是 [(𝙱𝙲𝚇𝚇𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,也就是最右边合理重现位置为 -5,即 𝑟𝑝𝑟(𝑗) = −5
;
对于 𝑟𝑝𝑟(1)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙲𝚇𝚇𝚇𝙰𝙱𝙲
,在 𝑝𝑎𝑡[1]
之前的最右边的合理重现是 [(𝙲𝚇𝚇𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) = −4
;
对于 𝑟𝑝𝑟(2)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚇𝚇𝚇𝙰𝙱𝙲
,在 𝑝𝑎𝑡[2]
之前的最右边的合理重现是 [(𝚇𝚇𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) = −3
;
对于 𝑟𝑝𝑟(3)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚇𝚇𝙰𝙱𝙲
,在 𝑝𝑎𝑡[3]
之前的最右边的合理重现是 [(𝚇𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) = −2
;
对于 𝑟𝑝𝑟(4)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚇𝙰𝙱𝙲
,在 𝑝𝑎𝑡[4]
之前的最右边的合理重现是 [(𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) = −1
;
对于 𝑟𝑝𝑟(5)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙰𝙱𝙲
,在 𝑝𝑎𝑡[5]
之前的最右边的合理重现是 [𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) =0
;
对于 𝑟𝑝𝑟(6)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙱𝙲
,又因为 𝑠𝑡𝑟𝑖𝑛𝑔[0] =𝑠𝑡𝑟𝑖𝑛𝑔[6]
,即 𝑠𝑡𝑟𝑖𝑛𝑔[0]
等于失配字符 𝑠𝑡𝑟𝑖𝑛𝑔[6]
,所以 𝑠𝑡𝑟𝑖𝑛𝑔[0…2]
并不是符合条件的 𝑠𝑢𝑏𝑝𝑎𝑡
的合理重现,所以在最右边的合理重现是 [(𝙱𝙲)]𝙰𝙱𝙲𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) = −2
;
对于 𝑟𝑝𝑟(7)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙲
,同理又因为 𝑠𝑡𝑟𝑖𝑛𝑔[7] =𝑠𝑡𝑟𝑖𝑛𝑔[1]
,所以 𝑠𝑡𝑟𝑖𝑛𝑔[1…2]
并不是符合条件的 𝑠𝑢𝑏𝑝𝑎𝑡
的合理重现,在最右边的合理重现是 [(𝙲)]𝙰𝙱𝙲𝚇𝚇𝚇𝙰𝙱𝙲
,所以 𝑟𝑝𝑟(𝑗) = −1
;
对于 𝑟𝑝𝑟(8)
,根据 𝑑𝑒𝑙𝑡𝑎2
定义,𝑟𝑝𝑟(𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠) =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠
,得到 𝑟𝑝𝑟(8) =8
。
现在再看一下另一个例子:
𝑗: 𝟶 𝟷 𝟸 𝟹 𝟺 𝟻 𝟼 𝟽 𝟾𝑝𝑎𝑡: 𝙰 𝙱 𝚈 𝚇 𝙲 𝙳 𝙴 𝚈 𝚇𝑟𝑝𝑟(𝑗): 𝟾 𝟽 𝟼 𝟻 𝟺 𝟹 𝟸 𝟷 𝟾𝑠𝑔𝑛: - - - - - - + - +
对于 𝑟𝑝𝑟(0)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,在 𝑝𝑎𝑡[0]
之前的最右边合理重现只能是 [(𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,也就是最右边合理重现位置为 -8,即 𝑟𝑝𝑟(𝑗) = −8
;
对于 𝑟𝑝𝑟(1)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,在 𝑝𝑎𝑡[1]
之前的最右边合理重现只能是 [(𝚈𝚇𝙲𝙳𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) = −7
;
对于 𝑟𝑝𝑟(2)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚇𝙲𝙳𝙴𝚈𝚇
,在 𝑝𝑎𝑡[2]
之前的最右边合理重现只能是 [(𝚇𝙲𝙳𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) = −6
;
对于 𝑟𝑝𝑟(3)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙲𝙳𝙴𝚈𝚇
,在 𝑝𝑎𝑡[3]
之前的最右边合理重现只能是 [(𝙲𝙳𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) = −5
;
对于 𝑟𝑝𝑟(4)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙳𝙴𝚈𝚇
,在 𝑝𝑎𝑡[4]
之前的最右边合理重现只能是 [(𝙳𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) = −4
;
对于 𝑟𝑝𝑟(5)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝙴𝚈𝚇
,在 𝑝𝑎𝑡[5]
之前的最右边合理重现只能是 [(𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) = −3
;
对于 𝑟𝑝𝑟(6)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚈𝚇
,因为 𝑠𝑡𝑟𝑖𝑛𝑔[2…3] =𝑠𝑡𝑟𝑖𝑛𝑔[7…8]
并且有 𝑠𝑡𝑟𝑖𝑛𝑔[6] ≠𝑠𝑡𝑟𝑖𝑛𝑔[1]
,所以在 𝑝𝑎𝑡[6]
之前的最右边的合理重现是 𝙰𝙱[𝚈𝚇]𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) =2
;
对于 𝑟𝑝𝑟(7)
,𝑠𝑢𝑏𝑝𝑎𝑡
为 𝚇
,虽然 𝑠𝑡𝑟𝑖𝑛𝑔[3] =𝑠𝑡𝑟𝑖𝑛𝑔[8]
但是因为 𝑠𝑡𝑟𝑖𝑛𝑔[2] =𝑠𝑡𝑟𝑖𝑛𝑔[7]
,所以在 𝑝𝑎𝑡[7]
之前的最右边的合理重现是 [𝚇]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,𝑟𝑝𝑟(𝑗) = −1
;
对于 𝑟𝑝𝑟(8)
,根据 𝑑𝑒𝑙𝑡𝑎2
定义,𝑟𝑝𝑟(𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠) =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠
,得到 𝑟𝑝𝑟(8) =8
。
对匹配算法的一个改进
最后,实践过程中考虑到搜索过程中估计有 80% 的时间用在了 观察 1 的跳转上,也就是 𝑠𝑡𝑟𝑖𝑛𝑔[𝑖]
和 𝑝𝑎𝑡[𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠]
不匹配,然后跳跃整个 𝑝𝑎𝑡𝑙𝑒𝑛
进行下一次匹配的过程。
于是,可以为此进行特别的优化:
我们定义一个 𝑑𝑒𝑙𝑡𝑎0
:
𝐢𝐧𝐭 𝑑𝑒𝑙𝑡𝑎0(𝐜𝐡𝐚𝐫 𝑐ℎ𝑎𝑟)𝐢𝐟 𝑐ℎ𝑎𝑟=𝑝𝑎𝑡[𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠]𝐫𝐞𝐭𝐮𝐫𝐧 𝑙𝑎𝑟𝑔𝑒 // large为一个整数,需要满足large>stringlastpos+patlen𝐫𝐞𝐭𝐮𝐫𝐧 𝑑𝑒𝑙𝑡𝑎1(𝑐ℎ𝑎𝑟)
用 𝑑𝑒𝑙𝑡𝑎0
代替 𝑑𝑒𝑙𝑡𝑎1
,得到改进后的匹配算法:
𝑖←𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠𝐥𝐨𝐨𝐩𝐢𝐟 𝑖>𝑠𝑡𝑟𝑖𝑛𝑔𝑙𝑎𝑠𝑡𝑝𝑜𝑠𝐫𝐞𝐭𝐮𝐫𝐧 𝑓𝑎𝑙𝑠𝑒𝐰𝐡𝐢𝐥𝐞 𝑖<𝑠𝑡𝑟𝑖𝑛𝑔𝑙𝑒𝑛𝑖←𝑖+𝑑𝑒𝑙𝑡𝑎0(𝑠𝑡𝑟𝑖𝑛𝑔(𝑖)) // 除非string[i]和pat末尾字符匹配,否则至多向下滑动patlen 𝐢𝐟 𝑖⩽ 𝑙𝑎𝑟𝑔𝑒//此时表示string上没有一个字符和pat末尾字符匹配 𝐫𝐞𝐭𝐮𝐫𝐧 𝑓𝑎𝑙𝑠𝑒𝑖←𝑖−𝑙𝑎𝑟𝑔𝑒𝑗←𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠.𝐰𝐡𝐢𝐥𝐞 𝑗⩾ 0 𝑎𝑛𝑑 𝑠𝑡𝑟𝑖𝑛𝑔[𝑖]=𝑝𝑎𝑡[𝑗]𝑗←𝑗−1𝑖←𝑖−1𝐢𝐟 𝑗<0𝐫𝐞𝐭𝐮𝐫𝐧 𝑖+1𝑖←𝑖+𝑚𝑎𝑥(𝑑𝑒𝑙𝑡𝑎1(𝑠𝑡𝑟𝑖𝑛𝑔[𝑖]),𝑑𝑒𝑙𝑡𝑎2(𝑗))
其中 𝑙𝑎𝑟𝑔𝑒
起到多重作用,一是类似后面介绍的 Horspool 算法进行快速的坏字符跳转,二是辅助检测字符串搜索是否完成。
经过改进,比起原算法,在做 观察 1 跳转时不必每次进行 𝑑𝑒𝑙𝑡𝑎2
的多余计算,使得在通常字符集下搜索字符串的性能有了明显的提升。
delta2 构建细节
引入
在 1977 年 10 月的Communications of the ACM上,Boyer、Moor 的论文[^bm]中只描述了 𝑑𝑒𝑙𝑡𝑎2
静态表,
构造 𝑑𝑒𝑙𝑡𝑎2
的具体实现的讨论出现在 1977 年 6 月 Knuth、Morris、Pratt 在SIAM Journal on Computing上正式联合发表的 KMP 算法的论文[^kmp]。
朴素算法
在介绍 Knuth 的 𝑑𝑒𝑙𝑡𝑎2
构建算法之前,根据定义,我们会有一个适用于小规模问题的朴素算法:
- 对于
[0, patlen)
区间的每一个位置 i
,根据 subpat
的长度确定其重现位置的区间,也就是 [-subpatlen, i]
;
- 可能的重现位置按照从右到左进行逐字符比较,寻找符合 𝑑𝑒𝑙𝑡𝑎2
要求的最右边 𝑠𝑢𝑏𝑝𝑎𝑡
的重现位置;
- 最后别忘了令 𝑑𝑒𝑙𝑡𝑎2(𝑙𝑎𝑠𝑡𝑝𝑜𝑠) =0
。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | use std::cmp::PartialEq;
pub fn build_delta_2_table_naive(p: &[impl PartialEq]) -> Vec<usize> {
let patlen = p.len();
let lastpos = patlen - 1;
let mut delta_2 = vec![];
for i in 0..patlen {
let subpatlen = (lastpos - i) as isize;
if subpatlen == 0 {
delta_2.push(0);
break;
}
for j in (-subpatlen..(i + 1) as isize).rev() {
// subpat 匹配
if (j..j + subpatlen)
.zip(i + 1..patlen)
.all(|(rpr_index, subpat_index)| {
if rpr_index < 0 {
return true;
}
if p[rpr_index as usize] == p[subpat_index] {
return true;
}
false
})
&& (j <= 0 || p[(j - 1) as usize] != p[i])
{
delta_2.push((lastpos as isize - j) as usize);
break;
}
}
}
delta_2
}
|
特别地,对 Rust 语言特性进行必要地解释,下不赘述:
usize
和 isize
是和内存指针同字节数的无符号整数和有符号整数,在 32 位机上相当于 u32
和 i32
,64 位机上相当于 u64
和 i64
。
- 索引数组、向量、分片时使用
usize
类型的数字(因为在做内存上的随机访问并且下标不能为负值),所以如果需要处理负值要用 isize
,而进行索引时又要用 usize
,这就看到使用 as
关键字进行二者之间的显式转换。
impl PartialEq
只是用作泛型,可以同时支持 Unicode
编码的 char
和二进制的 u8
。
显然,该暴力算法的时间复杂度为 𝑂(𝑛3)
。
高效算法
下面我们要介绍的是时间复杂度为 𝑂(𝑛)
,但是需要额外 𝑂(𝑛)
空间复杂度的高效算法。
虽然 1977 年 Knuth 提出了这个构建方法,然而他的原始版本的构建算法存在一个缺陷,实际上对于某些 𝑝𝑎𝑡
产生不出符合定义的 𝑑𝑒𝑙𝑡𝑎2
。
Rytter 在 1980 年SIAM Journal on Computing上发表的文章[^rytter]对此提出了修正,以下是 𝑑𝑒𝑙𝑡𝑎2
的构建算法:
首先考虑到 𝑑𝑒𝑙𝑡𝑎2
的定义比较复杂,我们按照 𝑠𝑢𝑏𝑝𝑎𝑡
的重现位置进行分类,每一类进行单独处理,这是高效实现的关键思路。
按照重现位置由远到近,也就是偏移量由大到小,分成如下几类:
-
整个 𝑠𝑢𝑏𝑝𝑎𝑡
重现位置完全在 𝑝𝑎𝑡
左边的,比如 [(𝙴𝚈𝚇)]𝙰𝙱𝚈𝚇𝙲𝙳𝙴𝚈𝚇
,此时 𝑑𝑒𝑙𝑡𝑎2(𝑗) =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 ×2 −𝑗
;
-
𝑠𝑢𝑏𝑝𝑎𝑡
的重现有一部分在 𝑝𝑎𝑡
左边,有一部分是 𝑝𝑎𝑡
头部,比如 [(𝚇𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,此时 𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 <𝑑𝑒𝑙𝑡𝑎2(𝑗) <𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 ×2 −𝑗
;
我们把 𝑠𝑢𝑏𝑝𝑎𝑡
完全在 𝑝𝑎𝑡
头部的的边际情况也归类在这里(当然根据实现也可以归类在下边),比如 [𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,此时 𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 =𝑑𝑒𝑙𝑡𝑎2(𝑗)
;
-
𝑠𝑢𝑏𝑝𝑎𝑡
的重现完全在 𝑝𝑎𝑡
中,比如 𝙰𝙱[𝚈𝚇]𝙲𝙳𝙴𝚈𝚇
,此时 𝑑𝑒𝑙𝑡𝑎2(𝑗) <𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠
。
现在来讨论如何高效地计算这三种情况:
第一种情况
这是最简单的情况,只需一次遍历并且可以顺便将 𝑑𝑒𝑙𝑡𝑎2
初始化。
第二种情况
我们观察什么时候会出现 𝑠𝑢𝑏𝑝𝑎𝑡
的重现一部分在 𝑝𝑎𝑡
左边,一部分是 𝑝𝑎𝑡
的头部的情况呢?应该是 𝑠𝑢𝑏𝑝𝑎𝑡
的某个后缀和 𝑝𝑎𝑡
的某个前缀相等,
比如之前的例子:
𝑗: 𝟶 𝟷 𝟸 𝟹 𝟺 𝟻 𝟼 𝟽 𝟾𝑝𝑎𝑡: 𝙰 𝙱 𝙲 𝚇 𝚇 𝚇 𝙰 𝙱 𝙲
𝑑𝑒𝑙𝑡𝑎2(3)
的重现 [(𝚇𝚇)𝙰𝙱𝙲]𝚇𝚇𝚇𝙰𝙱𝙲
,𝑠𝑢𝑏𝑝𝑎𝑡
𝚇𝚇𝙰𝙱𝙲
的后缀与 pat 前缀中,有相等的,是 𝙰𝙱𝙲
。
实际上,对第二种和第三种情况的计算的关键都需要前缀函数的计算和和应用。
那么只要 𝑗
取值使得 𝑠𝑢𝑏𝑝𝑎𝑡
包含这个相等的后缀,那么就可以得到第二种情况的 𝑠𝑢𝑏𝑝𝑎𝑡
的重现,对于例子,我们只需要使得 𝑗 ⩽5
,
而当 𝑗 =5
时,就是 𝑠𝑢𝑏𝑝𝑎𝑡
完全在 𝑝𝑎𝑡
头部的边际情况。
可以计算此时的 𝑑𝑒𝑙𝑡𝑎2(𝑗)
:
设此时这对相等的前后缀长度为 𝑝𝑟𝑒𝑓𝑖𝑥𝑙𝑒𝑛
,可知 𝑠𝑢𝑏𝑝𝑎𝑡𝑙𝑒𝑛 =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −𝑗
,那么在 𝑝𝑎𝑡
左边的部分长度是 𝑠𝑢𝑏𝑝𝑎𝑡𝑙𝑒𝑛 −𝑝𝑟𝑒𝑓𝑖𝑥𝑙𝑒𝑛
,
而 𝑟𝑝𝑟(𝑗) = −(𝑠𝑢𝑏𝑝𝑎𝑡𝑙𝑒𝑛 −𝑝𝑟𝑒𝑓𝑖𝑥𝑙𝑒𝑛)
,所以得到 𝑑𝑒𝑙𝑡𝑎2(𝑗) =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 −𝑟𝑝𝑟(𝑗) =𝑝𝑎𝑡𝑙𝑎𝑠𝑡𝑝𝑜𝑠 ×2 −𝑗 −𝑝𝑟𝑒𝑓𝑖𝑥𝑙𝑒𝑛
。
其后面可能会有多对相等的前缀和后缀,比如:
𝑗: 𝟶 𝟷 𝟸 𝟹 𝟺 𝟻 𝟼 𝟽 𝟾 𝟿𝑝𝑎𝑡: 𝙰 𝙱 𝙰 𝙰 𝙱 𝙰 𝙰 𝙱 𝙰 𝙰
在 𝑗 ≤2
处有 𝙰𝙱𝙰𝙰𝙱𝙰𝙰
,2 <𝑗 ≤5
处有 𝙰𝙱𝙰𝙰
,在 $5
本页面最近更新:2025/9/14 21:22:43,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Enter-tainer, minghu6, Tiphereth-A, HeRaNO, alphagocc, c0nstexpr, CCXXXI, Chrogeek, Early0v0, githuu5y5u, iamtwz, ksyx, megakite, r-value, wineee, Xeonacid, ZnPdCo
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用