MENU

Sunday算法

一:背景

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP,BM的实现容易太多。

阅读全文

BFS和DFS

我们首次接触BFS和DFS时,应该是在数据结构课上讲的“图的遍历”。它们的实现都很简单,这里我就不哆嗦去贴代码了。我觉得读者更想知道的是,这两者“遍历”的序列到底有何差别?

那本篇文章就单纯来讲讲它们的区别和各自的应用,不会涉及任何代码。

广度优先搜索算法(Breadth-First-Search,缩写为BFS),是一种利用队列实现的搜索算法。简单来说,其搜索过程和“湖面丢进一块石头激起层层涟漪”类似。

深度优先搜索算法(Depth-First-Search,缩写为DFS),是一种利用递归实现的搜索算法。简单来说,其搜索过程和“不撞南墙不回头”类似。

BFS的重点在于队列,而DFS的重点在于递归。这是它们的本质区别。

举个典型例子,如下图,灰色代表墙壁,绿色代表起点,红色代表终点,规定每次只能走一步,且只能往下或右走。求一条绿色到红色的最短路径。

阅读全文

Boyer-Moore算法

一:背景

上一篇文章,我介绍了KMP算法

但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的"查找"功能(Ctrl+F),大多采用Boyer-Moore算法。Boyer-Moore算法不仅效率高,而且构思巧妙。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。

阅读全文

你被欺骗了很久:前缀和真前缀

相信很多读者都看过网上博客对KMP算法的讲解,其中必提及的一个名词就是:前缀。那么请问你心中理解的前缀的定义是什么呢?

对于字符串“china”,其前缀为:

china, chin, chi, ch, c

你的想法是不是和上面一样呢。但是我很遗憾地告诉你,KMP之前缀不是这样的,它是这样的:

chin, chi, ch, c

阅读全文