fucking-algorithm 有限状态机之 KMP 字符匹配算法

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

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

Dec 10 '21 02:12 utterances-bot

赞👍

Dec 10 '21 02:12 benyugit

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

Dec 25 '21 13:12 standingbychen

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

Jan 23 '22 09:01 deepbreath373

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

Feb 11 '22 13:02 fornobugworld

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

Mar 28 '22 00:03 zhongweiLeex

万一字符串含有中文呢

Mar 29 '22 09:03 viocha

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

Apr 15 '22 09:04 shanghua521

「影子状态」这段其实讲得不好，这里有更清楚的描述：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] 这个子字符串（去掉头 和 不匹配的尾），
输入状态机后所能走到的位置

Apr 17 '22 20:04 iwestlin

影子状态这个挺难的

Apr 23 '22 10:04 ltcxjtu

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

Jul 06 '22 20:07 massiachan

check in

Jul 09 '22 09:07 deepbreath373

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

Jul 12 '22 13:07 HauZeeLi

由于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才会同时推进，此时如果同时开始推进，就代表【k~X】的字符=【l~j】的字符（k和l代表第一次匹配相同的位置，值不重要）,而c !== pat.charAt(X), 也有【k~X-1】的字符=【l~j-1】的字符，此时dp[j][c]就应该回退到X的位置，看dp[X][c]的选择