字符串匹配算法

1. BF算法

英文全称：Brute Force，也即暴力匹配算法。主要思路是：遍历主串，逐个子串与模式串进行比较。代码如下（kotlin编写）：

/**
 * 暴力匹配算法
 *
 * @param main 主串
 * @param pattern 模式串
 */
fun stringMatchBF(main: String, pattern: String): Int {
    var n = main.length
    var m = pattern.length
    if (n < m)
        return -1
    if (n == m) {
        if (main == pattern)
            return 0
        return -1
    }
    //遍历匹配
    var flag: Boolean
    for (i in 0..n - m) {
        flag = true
        for (j in pattern.indices) {
            if (main[i + j] != pattern[j]) {
                flag = false
                break
            }
        }
        if (flag) return i
    }
    return -1
}

时间复杂度：O(n*m)，其中 n 为主串长度，m 为模式串长度

2. RK算法

根据两位发明者 Rabin 和 Karp 的名字来命名。与 BF 算法其实类似，BF 算法在比较子串与模式串的时候，是遍历比较的，而如果我们算出子串的 hash 值，最后只需要比较子串与模式串的 hash 值是否一致，如果相等则说明找到了，与遍历相比只需要一个 hash 值比较判断就可完成。

这里的关键是 hash 算法，要非常高效，这样其性能才能好过 BF 算法。

/**
 * RK算法。为了方便，这里假设字符串只包含英文字符 [a-z]
 * 实际上字符串是任意的，这时我们需要找到一个高效的 hash 算法，并且 hash 冲突相对比较少
 * 
 * @param main 主串
 * @param pattern 模式串
 */
fun stringMatchRK(main: String, pattern: String): Int {
    var n = main.length
    var m = pattern.length
    if (n < m)
        return -1
    if (n == m) {
        if (main == pattern)
            return 0
        return -1
    }
    //模式串的 hash 值
    var patternHash = 0
    //我们将字符 a-z 分别对应 0-25，每位分别相加
    for (ch in pattern) {
        patternHash += ch - 'a'
    }
    //遍历匹配
    var subStrHash = -1
    for (i in 0..n - m) {
        if (subStrHash == -1) {
            subStrHash = 0
            //计算第一个子串的 hash 值
            for (j in 0 until m) {
                subStrHash += (main[j] - 'a')
            }
        } else {
            //主串的相邻2个子串，只是头尾字符不一样，这样计算非常节省时间
            subStrHash = subStrHash - (main[i - 1] - 'a') + (main[i + m - 1] - 'a')
        }
        if (subStrHash == patternHash) {
            //这里需要注意，如果产生 hash 冲突，实际上还需要将子串与模式串逐一匹配
            return i
        }
    }

    return -1
}

3. BM算法

fun findSubStr(mainString: String, patternString: String?): Int {
    if (patternString.isNullOrEmpty()) {
        return -1
    }
    if (mainString.length < patternString.length)
        return -1
    val n = mainString.length
    val m = patternString.length

    //构造坏字符hash表，模式串中的每个字符，在模式串中的位置。数组下标对应 ASCII 码值，初始值都为 -1
    //现在只考虑字符集比较少的情况，如果字符串字符集比较大的情况，则不是很适用
    val badCharHashTable = IntArray(256) { -1 }
    //数组下标对应的是好后缀子串 {u} 的长度，对应的值是模式串中与 {u} 相匹配的子串 {u*} 的起始下标值，初始值都为 -1
    val suffix = IntArray(m) { -1 }
    //用来记录模式串的后缀子串是否能够匹配模式串的前缀子串，数组下标对应的是后缀子串 {u} 的长度
    val prefix = BooleanArray(m) { false }
    for (i in patternString.indices) {
        badCharHashTable[patternString[i].toInt()] = i
    }
    //计算 suffix、 prefix 数组的值，逐步将模式串的子串 [0, i] 与模式串进行比较，求得公共后缀子串，i 取值范围[0, m - 1]
    for (i in 0 until m - 1) {
        var j = i
        var k = 0   //公共后缀子串的长度
        //计算公共后缀子串
        while (j >= 0 && patternString[j] == mainString[m - k - 1]) {
            j--
            k++
            suffix[k] = j + 1
        }
        //此时说明该子串既是前缀子串也是后缀子串
        if (j == -1) {
            prefix[k] = true
        }
    }

    var i = 0
    //从主串的位置 0 开始匹配，从左往右开始匹配，最多到位置 n-m 处结束
    while (i <= n - m) {
        //从后往前逐一匹配
        var j = m - 1
        while (j >= 0) {
            if (mainString[i + j] != patternString[j]) {
                //找到坏字符，j 就是主串中坏字符在模式串中对应的位置
                break
            }
            j--
        }
        //说明整个字符串都匹配成功了，直接找到模式串了
        if (j < 0) {
            return i
        }

        //计算模式串匹配往后挪动的距离，坏字符在主串中的位置是 i + j
        //需要找到主串中，是否还有另一个可匹配的字符，没有则为 -1
        var step1 = j - badCharHashTable[mainString[i + j].toInt()]

        //如果有好后缀，则可计算通过好后缀可移动多少步
        var step2 = 0
        if (j < m - 1) {
            //好后缀长度
            val goodSuffixLength = m - j - 1
            //说明该好后缀在模式串中能够匹配到其他子串
            if (suffix[goodSuffixLength] != -1) {
                step2 = j - suffix[goodSuffixLength] + 1
            } else {
                //好后缀的后缀子串起始位置从 j + 2 开始
                var r = j + 2
                while (r <= m -1) {
                    if (prefix[m - r]) {
                        step2 = r
                        break
                    }
                    r++
                }
            }
            if (step2 == 0)
                step2 = m
        }
        i += max(step1, step2)
    }
    return -1
}

4. KMP算法

fun kmp(mainString: String, patternString: String): Int {
    if (patternString.isNullOrEmpty()) {
        return -1
    }
    if (mainString.length < patternString.length)
        return -1
    val m = patternString.length
    var next = getNext(patternString)

    var j = 0
    for (i in mainString.indices) {
        while (j > 0 && mainString[i] != patternString[j]) {
            j = next[j - 1] + 1
        }
        if (mainString[i] == patternString[j]) {
            j++
        }
        if (j == m) {   //找到模式串了
            return i - m + 1
        }
    }
    return -1
}

//计算 next 数组
fun getNext(str: String): Array<Int> {
    var m = str.length
    var next = Array(str.length) { -1 }
    next[0] = -1
    var k = -1
    for (i in 1 until m) {
        while (k != -1 && str[k + 1] != str[i]) {
            k = next[k]
        }
        if (str[k + 1] == str[i]) {
            k++
        }
        next[i] = k
    }
    return next
}

5. AC自动机

private class AcNode(var data: Char) {
    var children = TreeMap<Char, AcNode>()
    var isEndChar = false
    var length = -1
    var fail: AcNode? = null
}

class AcTree() {

    class MatchInfo(val position: Int, val length: Int)

    private val root: AcNode = AcNode('/')

    //构建trie树
    fun insert(str: String?) {
        if (str.isNullOrEmpty())
            return
        var p = root
        for (i in str.indices) {
            var childNode = p.children[str[i]]
            if (childNode == null) {
                childNode = AcNode(str[i])
                p.children[str[i]] = childNode
            }
            p = childNode
        }
        p.isEndChar = true
        p.length = str.length
    }

    //构建失败指针
    fun buildFailPointer() {
        var queue: Queue<AcNode> = LinkedList()
        root.fail = null
        queue.add(root)
        while (queue.isNotEmpty()) {
            var p = queue.remove()
            for (pc in p.children.values) {
                if (pc == null)
                    continue
                if (p == root) {
                    pc.fail = root
                } else {
                    var q = p.fail
                    while (q != null) {
                        var qc = q.children[pc.data]
                        if (qc != null) {
                            pc.fail = qc
                            break
                        }
                        q = q.fail
                    }
                    if (q == null) {
                        pc.fail = root
                    }
                }
                queue.add(pc)
            }
        }
    }

    //多模式传匹配
    fun match(str: String?): List<MatchInfo>? {
        if (str.isNullOrEmpty())
            return null
        val list = mutableListOf<MatchInfo>()
        var p: AcNode? = root
        for (i in str.indices) {
            while (p!!.children[str[i]] == null && p != root) {
                p = p.fail
            }
            p = p.children[str[i]]
            if (p == null) {
                p = root
            }
            var tmp = p
            while (tmp != root) {
                if (tmp!!.isEndChar) {
                    var pos = i - tmp!!.length + 1
                    list.add(MatchInfo(pos, tmp.length))
                }
                tmp = tmp.fail
            }
        }
        return list
    }

}