算法:AC 自动机实现多模式匹配

一、引入

如果我们想要在字符串“hello”中查找“he”,可以用暴力匹配、KMP、BM 算法等,但是如果想要同时查找“he”和“el“,又该如何实现?

最简单的方式就是先查找一遍”he“,然后再查找一遍”el“,如下图所示:

但这种方式的效率显然很低。为了更高效地完成多个模式串的匹配,贝[......]

阅读全文

算法设计与分析总结

基本概念

  • 一个计算是能够在某种计算装置上机械地执行的一个操作序列。
  • 输入规模:计算问题的输入数据所占用存储单元的数量n。
  • 时间复杂度:计算过程执行的计算规则的个数表示成输入规模n的函数f(n)。
  • 空间复杂度:计算过程使用的不同存储单元的个数表示成输入规模n的函数g(n)。
  • P:存在多项式时间复杂度[......]

阅读全文

并查集的实现与性能优化

并查集是用于处理不相交集合的合并及查询问题,主要操作为:创建集合、合并两个不相交集合、判断两个元素是否属于同一个集合。

其中,判断两个元素是否属于同一个集合,可以这样考虑:为每个集合选一个代表元素,从而“判断两个元素是否属于同一个集合”就变成了“判断两个元素所在集合的代表元素是否相同”。

基本操[......]

阅读全文

栈的应用:四则运算表达式求值

1. 栈的特点

栈是计算机中非常基础而又极其重要的一种数据结构,许多算法的实现都离不开栈,它的特点是“先进后出”,也可以说“后进先出”。
打一个形象的比方:栈好比一个弹夹,最先放入的子弹只能最后打出;而最后放入的子弹则最先打出。

2. 中缀表达式和后缀表达式

我们生活中接触的表达式大部分都是中缀[......]

阅读全文