AC自动机算法是什么

小白 QA 2020-04-21 16:22:18 阅读(...)

AC自动机算法是字符串搜索算法,用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度,约为字符串的长度加所有匹配的数量。

在计算机科学中,Aho–Corasick 算法是由 Alfred V. Aho 和 Margaret J.Corasick 发明的字符串搜索算法,用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度,约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数,如果每个子串互相匹配(如字典为 a,aa,aaa,aaaa,输入的字符串为 aaaa),算法的时间复杂度会近似于匹配的二次函数。

AC自动机算法是什么

简介

AC 自动机算法主要依靠构造一个有限状态机(类似于在一个 trie 树中添加失配指针)来实现。这些额外的失配指针允许在查找字符串失败时进行回退(例如设 Trie 树的单词 cat 匹配失败,但是在 Trie 树中存在另一个单词 cart,失配指针就会指向前缀 ca),转向某前缀的其他分支,免于重复匹配前缀,提高算法效率。

当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用,在这种情况下,算法的时间复杂度为输入字符串长度和匹配数量之和。

UNIX 系统中的一个命令 fgrep 就是以 AC 自动机算法作为基础实现的。

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 搜索算法 search algorithm

    搜索算法是什么

    搜索算法是解决搜索问题的任何算法,即检索存储在某个数据结构中的信息,或者在问题域的搜索空间中计算的信息。这种结构的例子包括但不限于链表,数组数据结构或搜索树。合适的搜索算法通常取决于正在搜索的数据结构,并且还可能包括有关数据的先前知识。
  • 遗传算法是什么

    遗传算法是什么

    遗传算法(GA)是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。
  • 竞争算法是什么

    竞争算法是什么

    帝国竞争算法(imperialist competitive algorithm, ICA )是一种受帝国竞争行为启发的新的智能优化算法,它与粒子群优化(PSO)、蚁群(BCO)等算法一样,都属于基于群体的随机优化搜索算法。
  • 线性搜索 Linear search

    线性搜索是什么

    线性搜索或顺序搜索是一种寻找某一特定值的搜索算法,指按一定的顺序检查数组中每一个元素,直到找到所要寻找的特定值为止。是最简单的一种搜索算法。
  • 微信 WeChat

    帮朋友解封微信对自己有什么影响

    帮朋友解封微信对自己是没有影响的,您的账号只是验证对方账号是它所拥有的作用,只要按照微信解封的操作规则帮助你的微信好友验证身份;但是如果违规帮别人解封,那么可能会导致微信账号受限或被封号。
  • 统计 Statistics

    百度统计代码加到哪里

    百度统计代码需要加在网站全部页面的标签前,如果页面还使用了其他统计软件,需要加在其他代码之前;也可以放在网站首页底部,遵循原则是安装在公共代码中,便于全站都能检测数据;如果js文件中需要调用百度统计代码,需要去掉代码首尾后再放入JS文件中。