高度由习惯堆积

分类 算法:AC自动机 下的文章

March 3, 2019

HDU5069 Harry And Biological Teacher

题目As we all know, Harry Porter learns magic at Hogwarts School. However, learning magical knowledge alone is insufficient to become a great magician. Sometimes, Harry also has to gain knowledge fro...
February 24, 2019

AC自动机初步

概述应用场景:多模字符串匹配问题。KMP解决的问题是两个字符串之间的互相匹配,而如果有多个字符串要和一个字符串进行匹配呢?如果还用KMP的话,复杂度依然上天,所以,一个正常的想法是在KMP的基础上堆数据结构。所以AC自动机=在Trie树上跑KMP,它其中也存在失配数组,与KMP类似。初见AC自动机的基础是Trie树。和Trie树不同的是,树中的每个结点除了有指向孩子的指针(或者说引用),还有...