目的
在文本查找算法中，BM算法据说是最快的，号称亚线性。网上有很多的介绍，但大部分都是使用c语言构建，而且有些程序根本就不对。这里，经过整理和调试，将可用的kotlin版本贴出来，想用的可直接拿走。
算法简介
有比较好的博客对算法进行了介绍
- 字符串匹配的Boyer-Moore算法
-
## BM算法 Boyer-Moore高质量实现代码详解与算法详解
第一篇文章以图解的形式，详细的讲解了原理，基本上没有看不懂的地方，什么坏字符、好后缀、跳过的距离等。但是没有代码实现。
第二篇文章虽然也有图解，也有代码，但是有一处小错误，主要是坏字符跳转的时候，算法原理上要维护2维的跳转列表，但是为了实现方案一般都维护一个1维的，也就是说坏字符跳转的距离在存在好后缀的时候有可能会失效，但是由于有好后缀的移动距离，所以这个不存在问题。
kotlin代码
package com.davezhao.utils
class BmMatch(pattern: String) {
private val patternBytes = pattern.toByteArray()
private val patternSize = patternBytes.size
private val badSkip = MutableList((Byte.MAX_VALUE - Byte.MIN_VALUE + 1), { pattern.toByteArray().size })
private val goodSkip = MutableList(pattern.toByteArray().size, { patternSize })
init {
// 构建坏字符跳转记录表
var pLen = patternSize
for (b in patternBytes) {
badSkip[b - Byte.MIN_VALUE] = --pLen
}
// 构建好后缀跳转记录表
val suff = MutableList(patternSize, { patternSize })
for (i in (patternSize - 2 downTo 0)) {
var q = i
while (q >= 0 && patternBytes[q] == patternBytes[patternSize - 1 - i + q]) {
--q
}
suff[i] = i - q
}
for (i in (patternSize - 1 downTo 0)) {
if (suff[i] == i + 1) {
for (j in (0 until patternSize - 1 - i)) {
if (goodSkip[j] == patternSize) {
goodSkip[j] = patternSize - 1 - i
}
}
}
}
for (i in (0 until patternSize - 1)) {
goodSkip[patternSize - 1 - suff[i]] = patternSize - 1 - i
}
}
fun match(txt: String): List<Int> {
val txtBytes = txt.toByteArray()
val txtBytesSize = txtBytes.size
var txtIndex = 0
val res = mutableListOf<Int>()
while (txtIndex <= txtBytesSize - patternSize) {
var ptnIndex = patternSize - 1
while (ptnIndex >= 0 && patternBytes[ptnIndex] == txtBytes[ptnIndex + txtIndex]) {
--ptnIndex
}
if (ptnIndex < 0) {
res.add(txtIndex)
txtIndex += goodSkip[0]
} else {
txtIndex += maxOf(goodSkip[ptnIndex], badSkip[txtBytes[ptnIndex + txtIndex] - Byte.MIN_VALUE] - patternSize + 1 + ptnIndex)
}
}
return res
}
}
fun main(args: Array<String>) {
val bc = BmMatch("EBCDAB")
val res = bc.match("123EBCDAB45345112123453481567612345341565")
println(res)
}
输出为[3]，即在第四个byte位置找到了查找的字符串。
注意：如果输入的是unicode，也是给出byte的位置。
