文本查找BM算法kotlin实现

目的

在文本查找算法中，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的位置。