KMP 算法实现脏话屏蔽功能（Go 语言版）

先上代码：

package kmp

// KMP "a" is main string and "b" is model string
func KMP(a, b string) int {
    n := len(a)
    m := len(b)
    next := getNext(b)
    i, j := 0, 0
    for i < n && j < m {
        if j == -1 || a[i] == b[j] {
            i++
            j++
        } else {
            j = next[j]
        }
    }
    // totally match
    if j == m {
        return i - j
    }
    return -1
}

func getNext(b string) []int {
    m := len(b)
    next := make([]int, m, m)
    next[0] = -1
    next[1] = 0
    i, j := 0, 1 // start position
    for j < m-1 {
        if i == -1 || b[i] == b[j] {
            i++
            j++
            next[j] = i
        } else {
            i = next[i]
        }
    }
    return next
}

func KMPSearch(a, b string) int {
    if len(b) == 0 {
        return -1
    }
    if len(a) == 0 || len(a) < len(b) {
        return -1
    }
    if len(b) == 1 {
        i := 0
        for ; i < len(a); i++ {
            if a[i] == b[0] {
                return i
            }
        }
        return -1
    }
    return KMP(a, b)
}

package kmp

import (
    "github.com/magiconair/properties/assert"
    "strings"
    "testing"
)

func TestKMP(t *testing.T) {
    expected := "你好我*abc1234hell11111*hell****"
    a := "你好我日abc1234hell11111日hell日日日日"
    b := "日"
    pattern := "*"
    p := KMPSearch(a, b)
    if p != -1 {
        assert.Equal(t, strings.ReplaceAll(a, b, pattern), expected)
    } else {
        t.Log("not existed")
    }
}

KMP 算法的核心思想和 BM 算法非常相近，假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，试图找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

KMP 算法试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，找到一种规律，将模式串一次性滑动很多位。只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。

上面的代码中，最关键的是getNext 函数。getNext 生成一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。很多书中还给这个数组起了一个名字，叫失效函数（failure function）。

KMP 算法比 BF 算法实现起来要复杂的多，不过带来的好处是执行效率的提升，综合 KMP 算法实现函数和 next 数组生成函数，它的时间复杂度是 O(n+m)，其中 n 是主串长度，m 是子串长度，m 和 n 的值越大，与 BF 算法相比，性能越好，考虑到对于较长的主串，m 相对于 n 而言一般可以忽略，所以可以把 KMP 算法的时间复杂度近似看作 O(n)。