有限状态机之 KMP 字符匹配算法 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：有限状态机之 KMP 字符匹配算法

评论礼仪 见这里，违者直接拉黑。

[benyugit]

赞👍

[standingbychen]

影子状态这个名字好！X 与 j 就是如影随形的关系。

[deepbreath373]

盯着GIF看了半天，差点晕了😄

[fornobugworld]

搞定影子状态更新，就是一个标准动规，这个动规求得东西只是个辅助工具。是大问题的子问题，那三个元祖是真的猛啊。。

[zhongweiLeex]

提个小建议
东哥，您写的东西已经很完善了，就是小弟能否提个建议，就是能否在 二、状态机概述 那一part 加一个小小的说明，【关于状态转移依据，后面会补充】，不然看到这里是真的有点懵 😄 😭

[viocha]

万一字符串含有中文呢

[shanghua521]

如果想自己跟着代码走看流程的话，可以给算法精简一下只处理 a..i 之间的字符, pat.charAt 的时候 - 'a' 这样方便些

[iwestlin]

「影子状态」这段其实讲得不好，这里有更清楚的描述：https://juejin.cn/post/6856374004421722125
用我的话来形容：

X的本质，举例来说：
str = 'ababac'
pat = 'abac'
当二者一直匹配(aba)到不匹配（也就是b != c）时
理论上 pat 会从 str 的第二个字符开始 重新进行匹配，也就是 babac（去掉了头a
我们想知道能否直接得出（不匹配字符b之前的）已经计算过的 ba(同样去掉了头) 能走到 pat 的哪个位置
直接把 ba 输入已经生成的状态机中，可知道它能走到 a(也就是pat 的 X=1)
那么也就相当于我们可以从下面的 | 之后继续进行匹配了
aba|bac
  a|bac

综上，所以X保存的是
当遇到不匹配字符时(设其在pat中序号为n，从0开始)，
之前匹配的 pat[1] ~ pat[n - 1] 这个子字符串（去掉头 和 不匹配的尾），
输入状态机后所能走到的位置

[liushiqiang2000]

谢谢，一下子清晰好多

[ltcxjtu]

影子状态这个挺难的

[massiachan]

赞一个！写得很清楚，终于给整明白了

[deepbreath373]

check in

[HauZeeLi]

这个章节修改了,又来看了一遍.
关于选择尽可能大的质数Q,是不是就是选择小于Math.sqrt(Long.MAX_VALUE)的最大质数?
不然感觉乘法的地方有可能Long溢出.
东哥可以讲一下面试中遇到这种情况,具体怎么选择并计算出这个Q么

[turnflowerdown]

由于X和j一开始相差了1，所以X和j一定不会相遇（最接近的情况是一直有连续重复的字符，比如'aaaaa'，此时X和j始终相距1），而X的状态推进逻辑是，当dp[X][pat.charAt(j)] = X+1时，X才会推进（即X=dp[X][pat.charAt(j)]=X+1），而根据之前的dp定义，只有dp[X][pat.charAt(X)] 时才等于 X+1，可以得到pat.charAt(j) === pat.charAt(X)，即只有X位置的字符和j位置的字符相同时，X和j才会同时推进，此时如果同时开始推进，就代表【kX】的字符=【lj】的字符（k和l代表第一次匹配相同的位置，值不重要）,而c !== pat.charAt(X), 也有【kX-1】的字符=【lj-1】的字符，此时dp[j][c]就应该回退到X的位置，看dp[X][c]的选择

[turnflowerdown]

被转义了。。kX

[turnflowerdown]

~

[morganwu277]

lol 兄弟也是拼！给你点个赞

[l2009312042]

把gif转为图片序列看就不会晃眼了

[ShuyuanCao]

还是没有理解影子状态是如何得到的。。

[LebronHarden1]

东哥,以后能不能把gif改成那种点一下前进一步的样式,这样自己跳,也跟不上啊!

[lpdswing]

顶上去, 确实看的眼花

[yonggui-yan]

打半个卡
最后一步没看懂，明天再看一遍吧。

[angelyhch]

关于影子状态,理论上给来说,如果pat存在多种影子,那么应该在程序中增加影子1/影子2/影子3,从而优化算法.
这个理解对吗?

[MrRunShu]

谢谢拉哥，之前看KMP一直不懂，终于解决了一直困扰我的一个难题，哈哈

[cloudersecurity]

看了一天也没看懂影子状态，感觉我没救了

[morganwu277]

不是你没救了，是文章写的不好理解，如果一天没看懂，建议放弃本文章，找找其他文章。

[wubianxiaoxian]

swift 版本

class KMP {
    private var dp :[[Int]] = []
    private var pat: [Character] = []

    func kmp(_ value: String) {
        self.pat = Array(value)
        let m = pat.count
        let element = [Int](repeating: 0, count: 256)
        // dp[状态][字符] = 下个状态
        dp = [[Int]](repeating: element, count: m)
        // base case
        let v = Int(pat[0].asciiValue ?? 0)
        dp[0][v] = 1
        // 影子状态 X 初始为 0
        var x = 0
        // 构建状态转移图
        for j in 1..<m {
            for c in 0..<256 {
                dp[j][c] = dp[x][c]
            }
            let v = Int(pat[j].asciiValue ?? 0)
            dp[j][v] = j + 1
            // 更新影子状态
            x = dp[x][v]
        }
    }
    
    
    func serach(_ text: String) -> Int {
        let text = Array(text)
        let m  = pat.count, n = text.count
        // pat 的初始态为 0
        var j = 0
        for i in 0..<n {
            // 计算 pat 的下一个状态
            let v = Int(text[i].asciiValue ?? 0)
            j = dp[j][v]
            // 到达终止态，返回结果
            if j == m {
                return i - m + 1
            }
        }
        // 没到达终止态，匹配失败
        return -1
    }
}

[up-bear]

影子状态不太容易弄懂，需要跟着例子在脑子里过几遍。
东哥YYDS！！！

[chuyg1005]

应该是在pat[1:end]中找pat的第一次出现吧