字符串匹配之BF算法

ByWhat'sUs

字符串匹配之BF算法

BF 算法的原理很简单，在继续介绍之前，我们先引入两个术语：主串和模式串。简单来说，我们要在字符串 A 中查找子串 B，那么 A 就是主串，B 就是模式串。

作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，如果主串长度为 n，模式串长度为 m，我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

package main

import "fmt"

// BF 算法实现函数
func bfSearch(s, p string) int {
    begin := 0
    i, j := 0, 0
    n, m := len(s), len(p)  // 主串、子串长度
    for i = 0; i < n; begin++ {
        // 通过 BF 算法暴力匹配子串和主串
        for j = 0;j < m; j++ {
            if i < n && s[i] == p[j] {
                // 如果子串和主串对应字符相等，逐一往后匹配
                i++
            } else {
                // 否则退出当前循环，从主串下一个字符继续开始匹配
                break
            }
        }
        if j == m {
            // 子串遍历完，表面已经找到，返回对应下标
            return i - j
        }
        // 从下一个位置继续开始匹配
        i = begin
        i++
    }

    return -1
}

// 基于 BF 算法实现字符串查找函数
func strStrV1(haystack, needle string) int {
    // 子串长度=0
    if len(needle) == 0 {
        return 0
    }
    //主串长度=0，或者主串长度小于子串长度
    if len(haystack) == 0 || len(haystack) < len(needle) {
        return -1
    }
    // 调用 BF 算法查找子串
    return bfSearch(haystack, needle)
}

func main() {
    s := "Hello, nice to meet you!"
    p := "to"
    pos := strStrV1(s, p)
    fmt.Printf("Find \"%s\" at %d in \"%s\"\n", p, pos, s)
}

性能分析

这个算法很好理解，因为这就是我们正常都能想到的暴力匹配，BF 算法的时间复杂度最差是 O(n*m)，意味着要模式串要移到主串 n-m 的位置上，并且模式串每个字符都要与子串比较。