尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


主题:hexo-theme-lyrics
作者:尼采般地抒情

站点信息

文章数目:133
已运行时间:
目录
  1. Brute-Force
  2. KMP 算法

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


主题:hexo-theme-lyrics
作者:尼采般地抒情

站点信息

文章数目:133
已运行时间:
在进行字符串匹配的相关程序中,看一个子串是否在一个主串里面,有著名的Brute-Force和基于此改进的KMP算法,具体学习记录如下:

Brute-Force

给出一个主串和一个子串
主串:s = ababcabcacbab
子串:t = abcac

①BF 算法算是一种暴力算法,首先是查看 t 的第一字母 a 和上面 s 的第一个字母比较相同,所以接着比较比到各自的第三个字符也就是,aba、abc 发现不同,

② 再递推比较,t 回到第一个字母 a,这时 s 回到第二个字符(因为第一个字符已经比过了)相当于 babcabcacbab 和 abcac 两个字符串进行比较,很明显第一个字符就不一样,

③ 再递推比较……

按常理来思考,这样总能得出结果,但是在此基础上,可以有进一步的优化操作,怎么说?huaji1558a846ddf2e12b.jpeg
在上面的第 ② 步里面,我们总是一步一步递推,那我们能不能一次性推好几步呢?就根据已经匹配了的那串字母。

具体表现为:① 已经发现是第三个字符不同,那我们就根据前面两个相同的字符(ab)推出第 ② 步推两步,为什么根据相同的 ab,第 ② 个步骤就可以一次性走两步?

KMP 算法

版权声明:署名-非商业性使用-禁止演绎 4.0 国际 (CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/hcwio0/

评论区

Twikoo 转换 utterances

最新评论

Loading...