kmp算法

一如既往,推荐看客先看阮一峰博客:字符串匹配的KMP算法

定义:

一大串字符串里找某字段算法

原理:

利用某字段自身特有的规律(前后缀,这个词有看上面那文章或了解过算法的人才知道我说啥),实现非暴力查找字符串的方法。

重点:

得到部分匹配表

心得:

我用js根据思路写了个模拟的代码,能用!
源码地址:戳我

效率

嗯。。。没js自带的indexOf快。
测试时我的代码x ms,indexOf 是 0.x ms,快一倍(废话,原生的肯定用了更好的算法,比如从两头开始算,我这只从一头开始算)。

题外话

为什么会接触这个算法呢,本来我在看别人的源码,然后不小心点到他的知乎,又不小心点到他点过赞的文章,然后看到个文章大概是有个人面试时手写了kmp算法,面试官还问他是不是hr漏题了呵呵之类。。。,然后我正事没做(买了个慕课网的vue视频),就去看这算法了,发现别人的代码理解不了,然后去看阮一峰的博客,哦思想懂了!然后尝试写代码,index索引不太清楚该+1还是-1什么的就拿笔画一画,整个过程用3,4小时(我就是这渣渣水平)。

心态变化:我擦好难-我还看吗-不知浪不浪费时间-别人源码写的啥-理解这思路-自己写写看-成功-开心

想着对学习的朋友说下,有时看不懂别人的代码不要心急,可能。。。你理解后自己能写出来,再去看别人的代码(或不看)也可以哦,我是这样过来的,一起加油!

发表评论

电子邮件地址不会被公开。 必填项已用*标注