⚠️ 把假阳性揪出来
把一段字符折成一个数:h = (h * 31 + 字母序号) % 17,a 记 1、b 记 2、c 记 3。找出那些哈希对上了、字符却不一样的位置。
next 数组里存的是什么
KMP 先给模式算一张表,next[i] 存的是【0】。
⚠️ KMP 凭什么不用退文本指针
失配的时候,KMP 的文本指针一步都不退,靠的是【0】。
失配时模式该跳到哪
比到模式的第 k 个字符失配了,KMP 会去查 next 表,把 k 换成表里【0】。
ababc 的 next 表长什么样
一段文本 abababcababcabababc(19 个字符,下标从 0 起)和一个模式 ababc:把模式的 next 表算出来: T = "abababcababcabababc" P = "ababc&
自己写:把 next 表算出来
一段文本 abababcababcabababc(19 个字符,下标从 0 起)和一个模式 ababc:补全 build_next。
自己写:一个不回退的 KMP
一段文本 abababcababcabababc(19 个字符,下标从 0 起)和一个模式 ababc:补全 kmp。注意外层 for i 一路往前,从不回头。
🔴 KMP 的回退次数是零
一段文本 abababcababcabababc(19 个字符,下标从 0 起)和一个模式 ababc:把 KMP 的比较次数数出来,再记下文本指针最远走到哪个下标、以及回退了几次,和 n02 暴力的 39 次比较放在一起输出。
⚠️ 三种算法,位置必须一个不差
一段文本 abababcababcabababc(19 个字符,下标从 0 起)和一个模式 ababc:暴力、哈希、KMP 三种写法都已经给好了。把三个结果对一遍,输出位置和对账结论。
⚠️ 四个词各跑一次匹配,亏在哪
要在一段文本里找四个不同的词。每个词各跑一次 KMP,问题是【0】。