然8877线路检测中心后我们再了解下一步: ac自动机

当前位置:887700葡京线路检测 > 8877线路检测中心 > 然8877线路检测中心后我们再了解下一步: ac自动机
作者: 887700葡京线路检测|来源: http://www.hq8833.com|栏目:8877线路检测中心

文章关键词:887700葡京线路检测,自动机

  要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话会很浪费时间,所以AC自动机应运而生,如同Manacher一样,AC自动机利用某些操作阻止了模式串匹配阶段的回溯,将时间复杂度优化到了$O(n)$(n)为文本串长度

  下面开始用图学习ac自动机吧(个人比较喜欢放图,能用一张图解决的绝不叨叨) 首先给定模式串ash,shex,bcd,sha

  然后我们再了解下一步: ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如)是不是应该找的那一个) 一般,fail指针的构建都是用bfs实现的 首先每个模式串的首字母肯定是指向根节点的(一个字母你瞎指什么指,指了也是头字母有什么用嘛)

  注:经指出,最后一张图存在错误,8877线路检测中心最后的 h 应该指向 h 的下一节点 e,再由 e 指向根节点

  //让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!