最浅显易懂的 KMP 算法讲解

[@ZilongZheng-mp9mz]

感谢，这是我见过的解释KMP算法最好的视频。一般的讲解都是一上来就介绍最长相同前后缀和部分匹配数组的概念，弄得人一头雾水，这个视频非常尊重人的思维逻辑，循序渐进，一下子就弄明白了KMP算法，这个讲解的逻辑顺序非常好

[@chien5486]

講的好棒 謝謝你的用心 直到看到這篇才懂 影片聽起來又很像電影解說 很舒服 謝謝有你

[@AMlhd]

感谢分享!期待下一个佳作! 、

[@esc120]

第一次看到這麼好懂的 KMP 解說，太感謝了！！！😇

[@limlim4251]

这个时代有这个时代的中华文字发展趋势！唤醒大家是时候让世界容易学习中文，跟上国际大成员的中华简体文字发展步伐，没有必要一直复杂复杂复杂的旧体的繁体的。复杂旧体的繁体留给专家呀！ 群众聪明一起跟上中华近代文字发展步伐的简体中文，加油！

[@jackyyeh8763]

非常清楚易懂！ 感謝！

[@Frank-uk3tl]

next數組的 if-block要移到 prefix_len = next[preufx_len]上面 這樣才有機會繼續計算

[@wjchuang2487]

這個影片應該是華語解釋 KMP 算法最好的了! 只是動畫中最後在演示的時候， 如果把最後 C 與 B 不相同的下一步， 用 "AB" "A....B" 這樣表示可能會比較好。 當前用 "AB" "....AB" ，這和影片解釋的不太一致。 另外 next 數組的 if-block 要移到 prefix_len = next[preufx_len] 上面

[@chinchiang4345]

太厲害了!!跪著看完!!

[@CornuDev]

感謝分享，看懂了!!

[@chanandlerbong3090]

讲得很好，感谢！但是求next数组的部分似乎有问题，在else分支下应该加一个prefix_len是否大于0的判断才行吧？

[@wenluo9826]

确实需要加一个大于0的判定， 否则直接死循环了

[@xudongwz6962]

求next数组的函数有问题，对于这个pattern:"ababcaabc" ,求解到ababcaa最后这个a的时候按照图中的算法对应的next数组值为0，但是实际应该是1才对

[@wenluo9826]

刷算法题， 遇到相同的问题了，最后发现是next计算有问题🤣

[@qifang9221]

def build_next(patt): next = [0] prefix_len = 0 i = 1; while i < len(patt): if patt[prefix_len] == patt[i]: prefix_len += 1 next.append(prefix_len) i += 1 elif prefix_len > 0: prefix_len = next[prefix_len - 1] else: next.append(0) i += 1 return next 改成这样似乎可以？有可能当 prefix_len 等于 0 的时候，刚好 patt[prefix_len] == patt[i]，也就是你这个例子里面的最后这个 a，应当再进行第一个 if 的判断，如果再不匹配则 append 0

[@seayellow5834]

我还是比较好奇这个算法的可行性是怎么证明的

[@WangshengJi]

感谢

[@saber_archer]

您好，请问视频中的动画是用什么制作的，感觉比枯燥的代码有意思多了😂😂

[@ilemt0923]

這動畫是用3b1b的工具做的嗎？

[@劉彥廷-n5m]

Nice

[@programfan3719]

谢谢大佬，已经懂了😄

[@TiejunGao]

KMP 中的 P 我见过，还聊过天

[@pzzhuhui]

牛P

[@hcjet]

这频道不再更新可惜了

[@chunkwanchan5503]

simply the best

[@pzzhuhui]

在计算 build_next 时候，else prefix_len = next[prefix_len - 1]; prefix_len 初始值是0，分支走到这里，不是数据非法索引么？ 是 -1 啊

[@pzzhuhui]

@7:53 应该要加一个判断条件， if prefix_len > 0

[@chiaming859]

我一開始也有這個疑問，但-1其實是索引最後一個數，基本上會跑出-1的時候你上一次prefix_len為0，所以不會出錯，蠻巧妙的。

[@一块行尸走肉]

能不能把if prefix_len==0这个地方改成：while patt[prefix_len]==patt[i] or prefix_len==0来回退prefix_len呢？

[@jasonji1152]

build_next 我觉得可能过于精简 理解起来逻辑不是很直观。 这是我的修改(JS): function buildNext(needle) { const next = [0]; for (let i = 1; i < needle.length; i++) { // j表示目前为止(不包括[i])相同前后缀的长度 let j = next[i - 1]; // 查表 跳到能继续下去的更短的前后缀 while (needle[i] != needle[j] && j > 0) j = next[j - 1]; // 判断 if (needle[i] == needle[j]) { next[i] = j + 1; j++; } else { next[i] = 0; } } return next; }

[@wenluo9826]

判断相等那的j++已经没有用了

[@superheroherohero]

动画挺好

[@u1s172]

最后一个匹配的字符难道不是0😂？

[@jedywei]

Finite state machine

[@tianyuzhu7262]

else: i+=1是什么意思？

[@KeyboardKa1Ra]

else: i = i + 1