ac自动机_ac自动机模板 - CSDN
精华内容
参与话题
  • AC自动机-多模式匹配算法

    千次阅读 2016-08-24 12:05:15
    AC自动机  算法目的:  AC自动机主要用于解决多模式串的匹配问题,是字典树(trie树)的变种,一种伪树形结构(主体是树形的,但是由于加入了失败指针,使得它变成了一个有向图);trie图(我的理解^_^)是对AC自动机...

    AC自动机

           算法目的:

           AC自动机主要用于解决多模式串的匹配问题,是字典树(trie树)的变种,一种伪树形结构(主体是树形的,但是由于加入了失败指针,使得它变成了一个有向图);trie图(我的理解^_^)是对AC自动机的一种改造,使得图中每个结点都有MAXC条出边(MAXC表示该图的字符集合大小), trie图上的每个结点代表一个状态,并且和AC自动机的结点是一一对应的。

           算法核心思想:

           学习AC自动机(AC-Automan?艾斯奥特曼?-_-|||)之前,首先需要有字典树和KMP的基础,这是每一篇关于AC自动机的文章都会论及的,所以我也就例行提一下。

           例如,有四个01字符串(模式串),"01"、"10"、"110"、"11",字符集合为{'0', '1'}。那么构造trie图分三步,首先建立字典树,然后构造失败指针,最后通过失败指针补上原来不存在的边,那么现在就分三步来讨论如何构建一个完整的trie图。


    图1

           1) 字典树

           字典树是一种树形结构,它将所有的模式串组织在一棵树的树边上,它的根结点是一个虚根,每条树边代表一个字母,从根结点到任意一个结点的路径上的边的有序集合代表某个模式串的某个前缀

           如图1,绿色点为虚根,蓝色点为内部结点,红色点为终止结点,即从根结点到终止结点的每条路径代表了一个模式串,由于"11"是"110"的前缀,所以在图中"11"这两条边是这两个字符串路径的共用部分,这样就节省了存储空间,由于trie树的根结点到每个结点的路径(边权)都代表了一个模式串的前缀,所以它又叫前缀树。

           字典树实际上是一个DFA(确定性有限状态自动机),通常用转移矩阵表示。行表示状态,列表示输入字符,(行, 列)位置表示转移状态。这种方式的查询效率很高,但由于稀疏的现象严重,空间利用效率很低。所以一般采用压缩的存储方式即链表来表示状态转移,每个结点存储至少两个域:数据域data、子结点指针域next[MAXC](其中MAXC表示字符集总数)。

           构造字典树的前提一般是给定一系列的模式串,然后对每个模式串进行插入字典树的操作,初始情况下字典树只有一个虚根,如图2所示,进行四个模式串的插入后就完成了图1中的字典树的构造,每次插入在末尾结点打上标记(图中红色部分),可以注意到,第四次操作实际上没有生成新的结点,只是打了一个结尾标记,由于它的这个性质,使得字典树的结点数目不会很多,大大压缩了存储结构。具体实现方式和编码会在下文中详细讲解。


    图2

           2) 失败指针

           给定一个目标串,要求在由模式串构建的字典树中查找这个目标串中有多少个模式串,我们可以设定一个指针p,初始状态下它指向根结点,然后从前往后枚举目标串,对每一个目标串中的字符c,如果在p指向结点的出边集合中能够找到字符c对应的边,那么将p指向c对应边的子结点,循环往复,直到匹配失败,那么退回到p结点的fail指针指向的结点继续同样的匹配,当遇到一个终止结点时,计数器+1。

           这里的fail指针类似KMP的next函数,每个trie结点都有一个fail指针,如图3,首先将根结点的fail指针指向NULL,根结点的直接子结点的fail指针指向根结点,这一步是很显然的,因为当一个字符都不能匹配的时候肯定是要跳到字符串首重新匹配了,每个结点的fail指针都是由它父结点的fail指针决定的,所以一次BFS就可以把所有结点的fail指针逐层求解出来了,具体实现方式和编码会在下文中详细讲解。


    图3

           3) trie图

           为了方便描述,我们先把所有trie树上的结点进行编号,编号顺序为结点的插入顺序,根结点编号为0。如图4的第一个图,我们发现如果现在是1号状态(状态即结点),当接收一个'1'这个字符,那么它应该进入哪个状态呢?答案很显然,是2号状态,因为沿着字符'1'的出边到达的状态正好是2号状态;但是如果接受的是'0'字符,我们发现1号状态没有'0'字符代表的出边,所以我们需要补上这条'0'边,但是这条边指向哪个状态呢?答案是1号状态的fail指针指向的状态的'0'出边对应的状态。我们发现这个状态正好是它自己,所以向自己补一条边权为'0'的边(图中的橙色边,边指向的结点称为当前状态的后继状态)。同样是利用BFS的方式逐层求解所有结点的后继状态。我们发现所有结点遍历完后,每个结点都有且仅有两条出边,这样一个trie图就诞生了。


    图4

           今后几乎所有关于状态机的问题都是围绕图4的那个图展开的。

     

           新手初看算法的时候总是一头雾水,即使看懂了也要花很大力气才能把代码写出来(至少我是这样的),所以没有什么比直接阐述代码更加直观的了。

    一、结构定义

     1     #define MAXC 26
     2     // 结点结构
     3     struct ACNode {
     4     public:
     5         ACNode *fail;    // fail指针,指向和当前结点的某个后缀匹配的最长前缀的位置
     6         ACNode *next[MAXC];  // 子结点指针
     7 
     8         // 以下这些数据需要针对不同题目,进行适当的注释,因为可能内存会吃不消
     9 
    10         int id;   // 结点编号(每个结点有一个唯一编号)
    11         int val;  // 当前结点和它的fail指针指向结点的结尾单词信息的集合
    12         int cnt;  // 有些题中模式串有可能会有多个单词是相同的,但是计数的时候算多个
    13 
    14         void reset(int _id) {
    15             id = _id;
    16             val = 0;
    17             cnt = 0;
    18             fail = NULL;
    19             memset(next, 0, sizeof(next));
    20         }
    21 
    22         // 状态机中的 接收态 的概念
    23         // 模式串为不能出现(即病毒串)的时候才有接收态
    24         bool isReceiving() {
    25             return val != 0;
    26         }
    27     };

           对于trie树上的每个结点,保存了以下数据域:

           1) 结点编号 int id;

           每个结点的唯一标识,用于状态转移的时候的下标映射。

           2) 子结点指针 ACNode *next[MAXC];

           每个结点的子结点的个数就是字符串中字符集的大小,一般为26个英文字母,当然也有特殊情况,比如说和DNA有关的题,字符集为{ 'A'、'C'、'G'、'T' },那么字符集大小就为4;和二进制串有关的题,字符集大小就为2;而有的题则包含了所有的可见字符,所以字符集大小为256(有可能有中文字符...太BT了),这个就要视情况而定了。

           3) 失败指针 ACNode *fail;

           它的含义类似KMP中的最长前后缀的概念,即目标串在trie树上进行匹配的时候,如果在P结点上匹配失败,那么应该跳到P->fail继续匹配,如果还是失败,那么跳到P->fail->fail继续匹配,对于这个fail指针的构造,下文会详细讲解,这里先行跳过。

           4) 结尾标记 int cnt, val;

           每个模式串在进行插入的过程中,会对模式串本身进行一次线性的遍历,当遍历完毕即表示将整个串插入完毕,在结尾结点需要一个标记,表示它是一个模式串的末尾,有些问题会出现多个相同的模式串,所以用cnt来表示该串出现的次数,每插入一次对cnt进行一次自增;而有的题中,相同的模式串有不同的权值,并且模式串的个数较少(<= 15),那么可以将该结点是否是模式串的末尾用2的幂来表示,压缩成二进制的整数记录在val上(例如当前结点是第二个模式串和第四个模式串的结尾,则val = (1010)2)。

     1     class ACAutoman {
     2     public:
     3         /*结点相关结构*/
     4         ACNode* nodes[MAXQ];    // 结点缓存,避免内存重复申请和释放,节省时间
     5         int nodesMax;              // 缓冲区大小,永远是递增的 
     6         ACNode *root;             // 根结点指针
     7         int nodeCount;             // 结点总数
     8 
     9         /*数据相关结构*/
    10         int ID[256], IDSize;   // 结点上字母的简单HASH,使得结点编号在数组中连续
    11                            // 例如: ID['a']=0   ID['b']=1 依此类推
    12 
    13         /*队列相关结构*/
    14         ACNodeQueue Q;
    15 
    16     public:
    17         ACAutoman() {
    18             nodesMax = 0;
    19         }
    20         // 初始化!!! 必须调用
    21         void init() {
    22             nodeCount = 0;
    23             IDSize = 0;
    24             root = getNode();
    25             memset(ID, -1, sizeof(ID));
    26         }
    27 
    28         // 获取结点
    29         ACNode *getNode() {
    30             // 内存池已满,需要申请新的结点
    31             if(nodeCount >= nodesMax) {
    32                 nodes[nodesMax++] = new ACNode();
    33             }
    34             ACNode *p = nodes[nodeCount];
    35             p->reset(nodeCount++);
    36             return p;
    37         }
    38 
    39         // 获取字母对应的ID
    40         int getCharID(unsigned char c, int needcreate) {
    41             if(!needcreate) return ID[c];
    42             if(ID[c] == -1) ID[c] = IDSize++;
    43             return ID[c];
    44         }
    45     }AC;

           终于看到故事的主角(ACAutoman, 艾斯奥特曼)了,同样介绍一下它需要维护的数据结构:

           1) 结点缓存 ACNode* nodes[MAXQ];

           为了方便访问,我们将所有的结点组织在一个数组中,并且一开始不开辟空间,每次需要一个结点的时候,利用接口getNode()获取,类似内存池的概念,避免频繁申请和释放内存时候的时间开销。

           2) 根结点指针ACNode *root;

           trie树,既然是树,自然是有一个根结点的嘛。

           3) 结点总数 int nodeCount;

           4) 结点队列 ACNodeQueue Q;

           ACNodeQueue是自己实现的一个队列,数据域为ACNode *,主要是因为STL的效率实在不敢恭维,在某些OJ上效率极低,自己封装一套比较好,这个队列会在BFS的时候求失败指针时用到。

    二、模式串插入

     1     void ACAutoman ::insert(char *str, int val) {
     2         ACNode *p = root;
     3         int id;
     4         for(int i = 0; str[i]; i++) {
     5             // 获取字母对应的哈希ID
     6             id = getCharID(str[i], true);
     7             // 检查子结点是否存在,不存在则创建新的子结点
     8             if(p->next[id] == NULL) p->next[id] = getNode();
     9             p = p->next[id];
    10         }
    11         // 在这个单词的结尾打上一个标记
    12         p->val |= val;     // 注意有可能有相同的串
    13         p->cnt ++;
    14     }

           str为模式串,将它插入到trie树时,需要进行一次线性遍历,为了使每个字符访问方便,我们将字母映射到整数区间[0, IDSize)中,只要采用最简单的哈希即可。初始化当前结点p为根结点,对于字符串的某个字符,转换成整数id后,检测当前结点p是否存在id这个子结点,如果不存在则利用getNode()获取一个新的结点,并且让当前结点p的id子结点指向它,然后将当前结点转到它的id子结点上,继续上述操作。直到整个模式串枚举完毕,在结点p打上结束标记即可。

    三、失败指针、trie图 构造

     1     void construct_trie() {
     2         ACNode *now, *son, *tmp;
     3         
     4         root->fail = NULL;
     5         Q.clear();
     6         Q.push(root);
     7         
     8         // 逐层计算每一层的结点的fail指针
     9         // 当每个结点计算完毕,保证它所有后继都已经计算出来 
    10         while( !Q.empty() ) {
    11             now = Q.pop();
    12             
    13             if(now->fail) {
    14                 // 这里需要视情况而定
    15                 // 目的是将fail指针的状态信息传递给当前结点
    16                 // now->val += now->fail->val;
    17                 // now->val |= now->fail->val;
    18 
    19                 // 如果当前结点是个接收态,那么它的所有后继都是回到本身
    20                 if(now->isReceiving()) {
    21                     for(int i = 0; i < MAXC; i++) {
    22                         now->next[i] = now;
    23                     }
    24                     continue;
    25                 }
    26             }
    27             // 首先,我们把当前结点now的i号后继记为son[i]
    28             //   i) 如果son[i]不存在,将它指向 当前结点now的fail指针指向结点的i号后继(保证一定已经计算出来)。
    29             //   2) 如果son[i]存在,将它的fail指针指向 当前结点now的fail指针指向结点的i号后继(保证一定已经计算出来)。
    30             for(int i = 0; i < MAXC; i++) {
    31                 son = now->next[i];
    32                 tmp = (now == root) ? root : now->fail->next[i];
    33                 if(son == NULL) {
    34                     now->next[i] = tmp;
    35                 }else {
    36                     son->fail = tmp;
    37                     Q.push(son);
    38                 }
    39             }
    40         }
    41     }

           首先,讲一下失败指针的含义,因为之前提到,一个模式串的某个字符匹配失败的时候,就跳到它的失败指针上继续匹配,重复上述操作,直到这个字符匹配成功,所以失败指针一定满足一个性质,它指向的一定是某个串的前缀,并且这个前缀是当前结点所在前缀的后缀,而且一定是最长后缀。仔细理解一下这句话,首先,一定是某个串的前缀,这是显然的,因为trie树本来就是前缀树,它的任意一个结点都是某个模式串的前缀;然后再来看后面一句话,为了让当前字符能够找到匹配,那么当前结点的某个后缀必须要和某个模式串的前缀相匹配,这个性质就和KMP的next数组不谋而合了。

           然后,就是来看如何利用BFS求出所有结点的失败指针了。

     

           1) 对于根结点root的失败指针,我们将它直接指向NULL,对于根结点下所有的子结点,失败指针一定是指向root的,因为当一个字符都不能匹配的时候,自然也就不存在更短的能够与之匹配的前缀了;

           2) 将求完失败指针的结点插入队列中;

           3) 每次弹出一个结点now,询问它的每个字符对应的子结点,为了阐述方便,我们将now的i号子结点记为now->next[i]:

                  a) 如果now->next[i]为NULL,那么将now->next[i]指向now的失败指针的i号子结点, 即 now->next[i] = now->fail->next[i];

                  b) 如果now->next[i]不等于NULL,则需要构造now->next[i]的失败指针,由于a)的操作,我们知道now的失败指针一定存在一个i号子结点,即now->fail->next[i],那么我们将now->next[i]的失败指针指向它,即now->next[i]->fail = now->fail->next[i];

           4) 重复2)的操作直到队列为空;

    四、目标串匹配

     1     int query_str(char *str) {
     2         ACNode *p = root, *tmp = NULL;
     3         int id;
     4         int cnt = 0;
     5         
     6         for(int i = 0; str[i]; i++) {
     7             id = getCharID(str[i], false);
     8             if(id == -1) {
     9                 // 当前单词从来没有出现过,直接回到匹配之初
    10                 p = root;
    11                 continue;
    12             }
    13             p = p->next[id];
    14             tmp = p;
    15             while(tmp != root && tmp->cnt != -1) {
    16                 if(tmp->cnt) {
    17                     // 找到一个子串以tmp结点结尾
    18                     // 这里一般需要做题目要求的操作,不同题目不同
    19                     // 有的是统计子串数目、有的则是输出子串位置
    20                     cnt += tmp->cnt;
    21                     tmp->cnt = -1;
    22                 }
    23                 tmp = tmp->fail;
    24             }
    25         }
    26         return cnt;
    27     }

           对目标串进行匹配的时候,同样需要扫描目标字符串。由于trie图已经创建完毕,每个结点读入一个字符的时候都能够进入到下一个状态,所以我们只需要根据目标串给定的字符进行遍历,然后每次检查当前的结点是否是结尾结点,当然还需要检查p的失败指针指向的结点...累加所有的cnt和即为模式串的个数。

            对于AC自动机,各大OJ都有相关习题,来看几道比较经典的:

    HDU 2222 Keywords Search

    题意:给定N(N <= 10000)个长度不大于50的模式串,再给定一个长度为L(L <= 106)目标串,求目标串出现了多少个模式串。

    题解:AC自动机模板题,在每个trie结点存储一个count值,每次插入一个单词的时候对单词结尾结点的count值进行自增(不能将count值直接置为1,因为有可能模式串中有多个相同的串,它们是要被算作多次的),然后在询问的时候,每次计数完毕之后,将count值标为-1表示它已经被计算过了。最后输出所有count的累加和即可。

     

    HDU 2896 病毒侵袭

    题意:N(N <= 500)个长度不大于200的模式串(保证所有的模式串都不相同),M(M <= 1000)个长度不大于10000的待匹配串,问待匹配串中有哪几个模式串,题目保证每个待匹配串中最多有三个模式串。

    题解:构造trie树和fail指针,由于每个模式串都不同,所以每个代表模式串结尾的trie结点存储模式串对应的编号idx,扫描所有带匹配串,对于每个待匹配串利用失败指针模拟匹配,匹配的模式串个数到达三个的时候放弃扫描该串。

    可见字符包括空格,所以读入的时候需要用gets(),子结点个数为128。

     

    HDU 3065 病毒侵袭持续中

    题意:N(N <= 1000)个长度不大于50的模式串(保证所有的模式串都不相同),一个长度不大于2000000的待匹配串,求模式串在待匹配串中的出现次数。

    题解:由于每个病毒串不会完全相同,对于每个病毒串末尾记录一个编号标记,完全匹配后对编号对应的数组进行累加和计算。

     

    PKU 1204 Word Puzzles

    题意:给定一个L x C(C <= 1000, L <= 1000)的字母矩阵,再给定W(W <= 1000)个字符串,保证这些字符串都会在字母矩阵中出现(8种方向),求它们的出现位置和方向。

    题解:先缓存所有数据,然后对W个字符串建立字典树和失败指针,再扫描字母矩阵所有8个方向的字符串进行匹配。

     

    ZJY 3228 Searching the String

           题意:给定一个长度为N(N <= 105)的目标串,然后再给定M(M <= 105)个长度不大于6的字符串,问这些字符串在目标串的出现次数(分可重叠和不可重叠两种)。

           题解:将M个串作为模式串建立自动机,对于可重叠的情况直接询问即可,类似HDU 3065,不可重叠的情况需要记录每个串的长度Li以及之前这个串匹配到的最大位置Pi,对于当前位置Pos,如果P+ L<= Pos,那么认为和之前的一次匹配没有重叠,计数累加,并且更新P= Pos。

    为了方便,我把两种计算方式的模式串分别建立了两个自动机。


    PKU 3208 Apocalypse Someday

    题意:求第K(K <= 5*107)个有连续3个6的数。

    题解:建立DFA如下图,其中0为初态,1为非法状态(存在前导0),2为后缀没有6的状态,3、4、5分别为后缀有1个、2个、3个6的状态,所以5为接收态,因为一旦出现了3个6,那么无论接下来的是什么数都认为是合法数。


    既然有了状态转移图就可以轻松地利用状态转移方程求出长度为n有连续3个6的数字的个数,当长度小于等于L的满足条件的数字总数大于等于K的时候,就表明第K个满足条件的数字的长度为L,然后枚举每一位的数字判可行即可。


    PKU 2778 DNA Sequence

    题意:给定m(m <= 10)个DNA片段,每个串长度不超过10。求长度为N(N <= 2*109)的串中不包括任何给定的DNA片段的串的总数。

    题解:利用模式串建立trie图,将trie图转化为矩阵表示,利用二分求幂加速。

    为了更加直观,举例说明:

    例如,m=2,两个DNA片段分别为A和CAG,可以建立如下AC自动机:


    图5

    其中,灰色箭头代表树边,虚线代表失败指针,蓝色结点代表终止状态,0为起始状态。

    然后我们利用它来构造trie图,如图6。


    图6

    构造方法是利用BFS,依次处理每个状态可以到达哪些状态,建立可达矩阵。

    具体步骤如下:

    1) 初始状态入队。

    2) 每次弹出一个状态结点进行处理,直到队列为空。

    a) 对于当前处理的结点P,判断P是否是一个终止结点,如果不是,则判断P的fail指针指向的是否是一个终止结点,一直迭代到fail指针为空,如果迭代过程中找到某个结点为终止结点,那么表示P所在串的某个后缀包含了给定的DNA片段,那么标记P为终止结点,重复2),否则转b)。

    b) 枚举P的所有子结点Q[i](这里的子结点是包含所有字符集的):

    i) 如果Q[i]这个结点不为空,那么DFA[P][Q[i]] ++,Q[i]入队;

    ii) 否则沿着P的fail指针一直找,直到找到一个结点S的对应子结点T[i]不为空,那么DFA[P][T[i]]++,如果一直找不到,那么DFA[P][root]++;

    当队列为空的时候,有限状态自动机也就构造完毕了,按照这种方式,我们可以发现,除了终止状态,所有状态都有四条出边(A、C、G、T),但是终止状态并非真正意义上的终止状态,于是我们在终止状态上添加四条回边(指向自己),表示如果状态进入了终止状态就再也出不去了,这样一来,这个状态机就完整了,任意一个状态只要接收A、C、G、T四个字符中的一个就能进入下一个状态,这样就转化成了一个动态规划问题,假设状态方程DP[i][j]表示长度为i的串在j状态下的字符串个数,那么对于图2的状态机,有如下关系:

    DP[i][0] = 2 * DP[i-1][2] + 2 * DP[i-1][0];

    DP[i][1] = DP[i-1][0] + 4 * DP[i-1][1];

    DP[i][2] = DP[i-1][0] + DP[i-1][2];

    DP[i][3] = DP[i-1][2] + 4*DP[i-1][3];

    由于在DFA状态处理的时候3号状态为终止状态,所以DP[i][4]其实已经是一个冗余状态了,所以不列入讨论范围。

    按照递推方程,DP[N][0] + DP[N][2]就是我们要求的答案,但是N很大,所以可以将DP转移转化成矩阵,即:

     

    然后利用矩阵的二分求幂来加速了。

    这题更加直观的理解是:从起点0开始,走N步,经过的路径就是一个DNA串,如果最后到达的是终止状态,那么表示它包含了m个DNA片段中的至少一个。所有路径长度为N,终点非终止状态的路径数目之和就是我们要求的解。

    PKU 1625 Censored!

    题意:给定p(p <= 10)个长度不大于10的模式串,求长度为m(m <= 50)的串中不包含任何模式串的串的种类数。

    题解:首先利用模式串建立trie图,用DP[i][j]表示长度为i,状态为j的字符串的种类数,枚举所有字符进行状态转移即可。最后Sum{DP[m][i], i表示非终止状态} 就是答案,这题如果将字符直接进行下标映射,有可能会RE,就是它的字符的ASCII码有可能是在128-255之间的(例如中文),如果用scanf读入,转换成char就变成了负数,如果映射到下标就RE了,所以在映射之前最好先转成unsigned char。

     

    PKU 3691 DNA repair

           题意:给定N(N <= 50)个长度不超过20的模式串,再给定一个长度为M(M <= 1000)的目标串S,求在目标串S上最少改变多少字符,可以使得它不包含任何的模式串(所有串只有ACGT四种字符)。

           题解:利用模式串建立trie图,trie图的每个结点(即下文讲到的状态j)维护三个结构,

    Node{

           Node *next[4];   // 能够到达的四个状态 的结点指针

           int  id;         // 状态ID,用于到数组下标的映射

           int  val;        // 当前状态是否是一个非法状态 (以某些模式串结尾)

    }

     

    用DP[i][j]表示长度为i (i <= 1000),状态为j(j <= 50*20 + 1)的字符串变成目标串S需要改变的最少字符,设初始状态j = 0,那么DP[0][0] = 0,其它的DP[i][j]均为无穷大。从长度i到i+1进行状态转移,每次转移枚举共四个字符(A、C、G、T),如果枚举到的字符和S对应位置相同则改变值T=0,否则T=1;那么有状态转移方程 DP[i][j] = Min{ DP[i-1][ fromstate ] + T, fromstate为所有能够到达j的状态 };最后DP[n][j]中的最小值就是答案。

     

    PKU 1699 Best Sequence

           题意:给定N(N <= 10)个长度不超过20的模式串,求一个长度最短的串使得它包含所有的模式串。

           题解:利用模式串建立trie图,trie图的每个结点维护一个二进制权值,(val & 2i)不为0表示从根结点到该结点的某条路径上有第i个模式串,用DP[i][j]表示状态为i,模式串的二进制组合为j的最短串的长度,初始化DP[0][0] = 0,然后就转化成了一个在trie图上求(0, 0)到(i, 2n-1)点的最短路问题,最后求出来的DP[i][2n-1] (i < 200, 最多200个结点) 的最小值就是答案。

           注意:本题中的模式串有重复的情况需要特殊处理。

     

    HDU 2296 Ring

    题意:给定N (N <= 50) 和M(M <= 100)个长度不超过10的字符串以及每个字符串的权值Hi,求一个长度不超过N的字符串使得她包含的权值最大,如果有多个解输出长度最短的,如果还是有多个解,输出字典序最小的。

    题解:利用模式串建立trie图,用DP[i][j]表示长度为i,处于j状态下的字符串的最大权值,然后枚举26个字符进行状态转移,转移的过程中需要记录每个状态的前驱,每次进行最大值比较的时候,遇到最大值相等的情况则需要回溯,取字典序最小的。


    HDU 2825 Wireless Password

           题意:给定m(m <= 10)个长度不大于10的模式串,求长度为n(n <= 25)的至少包含k个模式串的字符串的种数,答案模上20090717。

           题解:类似PKU 1699利用模式串建立trie图,trie图上每个结点表示为一个状态,第i个模式串的权值为2i。用DP[i][j][l]表示长度为i,状态为j,已经有t个模式串的种类数(其中l表示这t个模式串的权值的位或),那么对于每个状态j,输入’a-z’这26个字符后必定能够到达下一个状态,从DP[0][0][0]=1开始迭代计算,最终SUM { DP[n][j][s] , s的二进制表示中1的个数大于等于k}就是答案。

    HDU 3341 Lost 's revenge

    题意:给定N(N <= 50)个长度不超过10的模式串(ACGT串),再给定一个长度为M(M <= 40)的目标串S,求将目标串重排列,使得它包含最多的模式串,求这个最多的数目。

    题解:利用模式串建立trie图,trie图上最多有500个结点( N*10 ),然后朴素的思想就是用S(i, iA, iC, iG, iT)表示在i状态下,拥有iA个A、iC个C、iG个G、iT个T的串拥有的最多的模式串的个数,但是iA, iC, iG, iT的取值均是[0, 40],所以我们需要把状态压缩一下,我们知道当四种字符都取10的时候可以让状态数达到最大,即114 = 14641, 所以可以令MaxA

    MaxC、MaxG、MaxT分别表示四种字符出现的个数,那么T字符的权值为1,G字符的权值为(Max+ 1),C字符的权值为(Max+ 1) *(Max+ 1),A字符的权值为(Max+ 1) *(Max+ 1) *(Max+ 1),进行进制压缩之后总的状态数不会超过114,可以用DP[i][j]表示在trie的i号结点时ACGT四个字符个数的压缩状态为j时的字符串包含模式串的最多数目,然后就是进行O(4*500*114)的状态转移了。

    HDU 2243 考研路茫茫——单词情结

    题意:给定N(N < 6)个长度不超过5的单词,求包含至少一个单词并且长度不超过L(L < 231)的字符串的种数。

    题解:利用PKU 2778的方法构造矩阵,由于求的是长度不超过L的种数,即长度为1、2、3...L,假设原有矩阵为M,那么构造一个新的矩阵M',它由两个原矩阵M,一个零矩阵O和一个单位阵I构成:

    该矩阵的右上角的子矩阵就是我们所求的方案矩阵,然后对 M' 二分求幂即可。这里需要总数模264,利用补码的性质,可以直接声明unsigned __int64直接运算即可,不需要用到大数。

     

    HDU 3247 Resource Archiver

           题意:给定n(n <= 10)个长度小于等于1000的源字符串以及m(m <= 1000)个病毒串(所有病毒串总长度不超过50000),求一个串使得它包含所有的源字符串并且不包含任何一个病毒串,求这个字符串的最短长度(所有的串保证都是01串)。

           题解:PKU 1699的加强版。

    PKU 4052 Hrinity

    题意:给定n(n <= 2500)个长度小于等于1100的模式串,求长度不大于5100000的目标串S中包含的模式串的数目,如果包含了模式串AB,并且BA的子串,那么只记录A

    题解:建立trie图,每个字符串结尾标记记录模式串编号,进行目标串匹配的时候,利用哈希将所有是目标串子串的模式串标记为1,然后枚举所有标记过的模式串,对他们进行模式匹配,利用同样的方法将模式串的所有模式串子串标记为0,最后统计有多少个模式串的标记为1就是答案了。

    展开全文
  • AC自动机 算法详解(图解)及模板

    万次阅读 多人点赞 2019-09-12 08:05:46
    ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针**转移**到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如`abce`和`...

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



    转载注明出自bestsort.cn,谢谢合作


    大家回复请去bestsort.cn回复吧,CSDN我每次都不知道你们回复的楼层在哪...点击查看评论它都不带自动跳转的QAQ

    下面开始用图学习ac自动机吧(个人比较喜欢放图,能用一张图解决的绝不叨叨)
    首先给定模式串"ash","shex","bcd","sha",然后我们根据模式串建立如下trie树:

    然后我们再了解下一步:
    ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如abcebcd,我们找到c发现下一个要找的不是e,就跳到bcd中的c处,看看此处的下一个字符(d)是不是应该找的那一个)

    一般,fail指针的构建都是用bfs实现的
    首先每个模式串的首字母肯定是指向根节点的(一个字母你瞎指什么指,指了也是头字母有什么用嘛)
    在这里插入图片描述
    现在第一层bfs遍历完了,开始第二层
    (根节点为第0层)第二层a的子节点为s,但是我们还是要从a-z遍历,如果不存在这个子节点我们就让他指向根节点(如下图红色的a)
    在这里插入图片描述
    当我们遍历到s的时候,由于存在s这个节点,我们就让他的fail指针指向他父亲节点(a)的fail指针指向的那个节点()的具有相同字母的子节点(第一层的s),也就是这样
    在这里插入图片描述
    按照相同规律构建第二层后,到了第三层的h点,还是按照上面的规则,我们找到h的父亲节点(s)fail指针指向的那个位置(第一层的s)然后指向它所指向的相同字母根->s->h的这个链的h节点,如下图
    在这里插入图片描述

    完全构造好后的树
    在这里插入图片描述
    然后匹配就很简单了,这里以ashe为例
    我们先用ash匹配,到h了发现:诶这里ash是一个完整的模式串,好的ans++,然后找下一个e,可是ash后面没字母了啊,我们就跳到hfail指针指向的那个h继续找,还是没有?再跳,结果当前的h指向的是根节点,又从根节点找,然而还是没有找到e,程序END

    过程如下图
    在这里插入图片描述


    喜闻乐见模板系列

    
    #include <queue>
    #include <cstdlib>
    #include <cmath>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn =  2*1e6+9;
    
    int trie[maxn][26]; //字典树
    int cntword[maxn];  //记录该单词出现次数
    int fail[maxn];     //失败时的回溯指针
    int cnt = 0;
    
    void insertWords(string s){
        int root = 0;
        for(int i=0;i<s.size();i++){
            int next = s[i] - 'a';
            if(!trie[root][next])
                trie[root][next] = ++cnt;
            root = trie[root][next];
        }
        cntword[root]++;      //当前节点单词数+1
    }
    void getFail(){
        queue <int>q;
        for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
            if(trie[0][i]){
                fail[trie[0][i]] = 0;
                q.push(trie[0][i]);
            }
        }
    
    //fail[now]    ->当前节点now的失败指针指向的地方
    tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
        while(!q.empty()){
            int now = q.front();
            q.pop();
    
            for(int i=0;i<26;i++){      //查询26个字母
                if(trie[now][i]){
                    //如果有这个子节点为字母i+'a',则
    //让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
                    //有点绕,为了方便理解特意加了括号
    
                    fail[trie[now][i]] = trie[fail[now]][i];
                    q.push(trie[now][i]);
                }
                else//否则就让当前节点的这个子节点
                    //指向当前节点fail指针的这个子节点
                    trie[now][i] = trie[fail[now]][i];
            }
        }
    }
    
    
    int query(string s){
        int now = 0,ans = 0;
        for(int i=0;i<s.size();i++){    //遍历文本串
            now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
            for(int j=now;j && cntword[j]!=-1;j=fail[j]){
                //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
                ans += cntword[j];
                cntword[j] = -1;    //将遍历国后的节点标记,防止重复计算
            }
        }
        return ans;
    }
    
    int main() {
        int n;
        string s;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> s ;
            insertWords(s);
        }
        fail[0] = 0;
        getFail();
        cin >> s ;
        cout << query(s) << endl;
        return 0;
    }
    
    
    
    展开全文
  • ac自动机最详细的讲解,让你一次学会ac自动机

    万次阅读 多人点赞 2018-12-03 22:16:18
    在没学ac自动机之前,觉得ac自动机是个很神奇,很高深,很难的算法,学完之后发现,ac自动机确实很神奇,很高深,但是却并不难。 我说ac自动机很神奇,在于这个算法中失配指针的妙处(好比kmp算法中的next数组),...

    在没学ac自动机之前,觉得ac自动机是个很神奇,很高深,很难的算法,学完之后发现,ac自动机确实很神奇,很高深,但是却并不难。
    我说ac自动机很神奇,在于这个算法中失配指针的妙处(好比kmp算法中的next数组),说它高深,是因为这个不是一般的算法,而是建立在两个普通算法的基础之上,而这两个算法就是kmp与字典树。所以,如果在看这篇博客之前,你还不会字典树或者kmp算法,那么请先学习字典树或者kmp算法之后再来看这篇博客。好了,闲话扯完了,下面进入正题。

    在学习一个新东西之前,一定要知道这个东西是什么,有什么用,我们学它的目的是什么,如果对这些东西没有一个清楚的把握,我不认为你能学好这个新知识。
    那么首先我们来说一下ac自动机是什么。下面是我从百度上找的。Aho-Corasick automaton,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。
    从上面我们可以知道,ac自动机其实就是一种多模匹配算法,那么你可能会问什么叫做多模匹配算法。下面是我对多模匹配的理解,与多模与之对于的是单模,单模就是给你一个单词,然后给你一个字符串,问你这个单词是否在这个字符串中出现过(匹配),这个问题可以用kmp算法在比较高效的效率上完成这个任务。那么现在我们换个问题,给你很多个单词,然后给你一段字符串,问你有多少个单词在这个字符串中出现过,当然我们暴力做,用每一个单词对字符串做kmp,这样虽然理论上可行,但是时间复杂度非常之高,当单词的个数比较多并且字符串很长的情况下不能有效的解决这个问题,所以这时候就要用到我们的ac自动机算法了。
    对于上面的文字,我已经回答了什么是多模匹配和我们为什么要学习ac自动机那就是ac自动机的作用是什么等一系列问题。下面是ac自动机的具体实现步骤以及模板代码。
    1.把所有的单词建立一个字典树。
    在建立字典树之前,我们先定义每个字典树上节点的结构体变量

    struct node{
        node *next[26];
        node *fail;
        int sum;
    };
    

    其中fail 是失配指针
    sum是这个节点是不是一个单词的结尾,以及相应的个数。
    下面是字典树的建立过程

    void Insert(char *s)
    {
        node *p = root;
        for(int i = 0; s[i]; i++)
        {
            int x = s[i] - 'a';
            if(p->next[x] == NULL)
            {
                newnode=(struct node *)malloc(sizeof(struct node));
                for(int j=0;j<26;j++) newnode->next[j] = 0;
                newnode->sum = 0;newnode->fail = 0;
                p->next[x]=newnode;
            }
            p = p->next[x];
        }
        p->sum++;
    }
    

    注意在建立字典树的过程中,先让每个节点的fail指针先为空。
    下面就是ac自动机最关键的一步,求解每个节点的失配指针,我在这里先说一下失配指针具体表示什么,每个节点的失配指针指向的是以当前节点表示的字符为最后一个字符的最长当前字符串的后缀字符串的最后一个节点。可能在这里你可能不怎么懂,没关系,光看上面的文字,肯定难以看懂,下面我用一个图来简单的表示一下,有助于你理解。

    假如我们有四个单词,abcd, bce, abd, cd,那么我们建立字典树如下:
    在这里插入图片描述
    首先我们让与根节点直接相连的节点的fail直接指向root,为了让你更好的理解fail指针,我们以节点x,y,z为例,我们让从图中我们可以看出x节点的fail指向了y节点,y节点的fail指向了z节点,为什么会这样指,因为x节点表示字符串abc,而字典树中含有最长,且以c结尾,且是abc的后缀的字符串bc(以y节点结尾的),同理,以y节点表示的字符串是bc,而以c结尾,且是bc的后缀的最长字符串是c(以z节点结尾的)。这就是fail指针指向的目标,那么我们得到了这个fail指针在匹配中有什么用呢,我们还是用上面的那个图来举例说明一下,假设文本串是abce,通过字典树我们可以看出,通过abc,所以我们可以匹配到x节点,但是到后面,我们发现d与e不匹配,这时我们就需要用到当前节点的fail了,因为x的fail指向的是y节点,所以我们直接跳到y节点,这是发现y节点后面有e,匹配上了,所以单词bce就在文本串abce中被检测出来了。当然这只是最简单的一种情况。
    下面是构造fail指针的具体代码。
    基于队列(bfs)实现的。

    void build_fail_pointer()
    {
        head = 0;
        tail = 1;
        q[head] = root;
        node *p;
        node *temp;
        while(head < tail)
        {
            temp = q[head++];
            for(int i = 0; i <= 25; i++)
            {
                if(temp->next[i])
                {
                    if(temp == root)
                    {
                        temp->next[i]->fail = root;
                    }
                    else
                    {
                        p = temp->fail;
                        while(p)
                        {
                            if(p->next[i])
                            {
                                temp->next[i]->fail = p->next[i];
                                break;
                            }
                            p = p->fail;
                        }
                        if(p == NULL) temp->next[i]->fail = root;
                    }
                    q[tail++] = temp->next[i];
                }
            }
        }
    }
    

    最后是利用前面求得的fail指针进行匹配。
    代码如下:

    void ac_automation(char *ch)
    {
        node *p = root;
        int len = strlen(ch);
        for(int i = 0; i < len; i++)
        {
            int x = ch[i] - 'a';
            while(!p->next[x] && p != root) p = p->fail;
            p = p->next[x];
            if(!p) p = root;
            node *temp = p;
            while(temp != root)
            {
               if(temp->sum >= 0)
               {
                   cnt += temp->sum;
                   temp->sum = -1;
               }
               else break;
               temp = temp->fail;
            }
        }
    }
    

    如果你还没有看懂ac自动机,没关系,细细品味,你一定能成功的。

    如果你看懂了上面的讲解,那么我们可以做一道模板题来试试,以hdu2222为例,ac代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e7 + 5;
    const int MAX = 10000000;
    int cnt;
    struct node{
        node *next[26];
        node *fail;
        int sum;
    };
    node *root;
    char key[70];
    node *q[MAX];
    int head,tail;
    node *newnode;
    char pattern[maxn];
    int N;
    void Insert(char *s)
    {
        node *p = root;
        for(int i = 0; s[i]; i++)
        {
            int x = s[i] - 'a';
            if(p->next[x] == NULL)
            {
                newnode=(struct node *)malloc(sizeof(struct node));
                for(int j=0;j<26;j++) newnode->next[j] = 0;
                newnode->sum = 0;newnode->fail = 0;
                p->next[x]=newnode;
            }
            p = p->next[x];
        }
        p->sum++;
    }
    void build_fail_pointer()
    {
        head = 0;
        tail = 1;
        q[head] = root;
        node *p;
        node *temp;
        while(head < tail)
        {
            temp = q[head++];
            for(int i = 0; i <= 25; i++)
            {
                if(temp->next[i])
                {
                    if(temp == root)
                    {
                        temp->next[i]->fail = root;
                    }
                    else
                    {
                        p = temp->fail;
                        while(p)
                        {
                            if(p->next[i])
                            {
                                temp->next[i]->fail = p->next[i];
                                break;
                            }
                            p = p->fail;
                        }
                        if(p == NULL) temp->next[i]->fail = root;
                    }
                    q[tail++] = temp->next[i];
                }
            }
        }
    }
    void ac_automation(char *ch)
    {
        node *p = root;
        int len = strlen(ch);
        for(int i = 0; i < len; i++)
        {
            int x = ch[i] - 'a';
            while(!p->next[x] && p != root) p = p->fail;
            p = p->next[x];
            if(!p) p = root;
            node *temp = p;
            while(temp != root)
            {
               if(temp->sum >= 0)
               {
                   cnt += temp->sum;
                   temp->sum = -1;
               }
               else break;
               temp = temp->fail;
            }
        }
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            root=(struct node *)malloc(sizeof(struct node));
            for(int j=0;j<26;j++) root->next[j] = 0;
            root->fail = 0;
            root->sum = 0;
            scanf("%d",&N);
            getchar();
            for(int i = 1; i <= N; i++)
            {
                gets(key);
                Insert(key);
            }
            gets(pattern);
            cnt = 0;
            build_fail_pointer();
            ac_automation(pattern);
            printf("%d\n",cnt);
        }
        return 0;
    }
    
    
    
    
    展开全文
  • AC自动机基本介绍

    千次阅读 2016-08-29 16:13:28
    AC自动机算法  转载自:http://blog.csdn.net/niushuai666/article/details/7002823 AC自动机简介:  首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模...

                                                               AC自动机

        转载自:http://blog.csdn.net/niushuai666/article/details/7002823
      AC自动机模板在我的后面一篇博客,也就是hdu2222入门题。

    AC自动机简介: 

    首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有字典树Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。

    AC自动机的构造:

    1.构造一棵Trie,作为AC自动机的搜索数据结构。

    2.构造fail指针,使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。如同 KMP算法一样, AC自动机在匹配时如果当前字符匹配失败,那么利用fail指针进行跳转。由此可知如果跳转,跳转后的串的前缀,必为跳转前的模式串的后缀并且跳转的新位置的深度(匹配字符个数)一定小于跳之前的节点。所以我们可以利用 bfs在 Trie上面进行 fail指针的求解。

    3.扫描主串进行匹配。

    AC自动机详讲:

    我们给出5个单词,say,she,shr,he,her。给定字符串为yasherhs。问多少个单词在字符串中出现过。

    一、Trie

    首先我们需要建立一棵Trie。但是这棵Trie不是普通的Trie,而是带有一些特殊的性质。

    首先会有3个重要的指针,分别为p, p->fail, temp。

    1.指针p,指向当前匹配的字符。若p指向root,表示当前匹配的字符序列为空。(root是Trie入口,没有实际含义)。

    2.指针p->fail,p的失败指针,指向与字符p相同的结点,若没有,则指向root。

    3.指针temp,测试指针(自己命名的,容易理解!~),在建立fail指针时有寻找与p字符匹配的结点的作用,在扫描时作用最大,也最不好理解。

    对于Trie树中的一个节点,对应一个序列s[1...m]。此时,p指向字符s[m]。若在下一个字符处失配,即p->next[s[m+1]] == NULL,则由失配指针跳到另一个节点(p->fail)处,该节点对应的序列为s[i...m]。若继续失配,则序列依次跳转直到序列为空或出现匹配。在此过程中,p的值一直在变化,但是p对应节点的字符没有发生变化。在此过程中,我们观察可知,最终求得得序列s则为最长公共后缀。另外,由于这个序列是从root开始到某一节点,则说明这个序列有可能是某些序列的前缀。

    再次讨论p指针转移的意义。如果p指针在某一字符s[m+1]处失配(即p->next[s[m+1]] == NULL),则说明没有单词s[1...m+1]存在。此时,如果p的失配指针指向root,则说明当前序列的任意后缀不会是某个单词的前缀。如果p的失配指针不指向root,则说明序列s[i...m]是某一单词的前缀,于是跳转到p的失配指针,以s[i...m]为前缀继续匹配s[m+1]。

    对于已经得到的序列s[1...m],由于s[i...m]可能是某单词的后缀,s[1...j]可能是某单词的前缀,所以s[1...m]中可能会出现单词。此时,p指向已匹配的字符,不能动。于是,令temp = p,然后依次测试s[1...m], s[i...m]是否是单词。

    构造的Trie为:


    二、构造失败指针

    用BFS来构造失败指针,与KMP算法相似的思想。

    首先,root入队,第1次循环时处理与root相连的字符,也就是各个单词的第一个字符h和s,因为第一个字符不匹配需要重新匹配,所以第一个字符都指向root(root是Trie入口,没有实际含义)失败指针的指向对应下图中的(1),(2)两条虚线;第2次进入循环后,从队列中先弹出h,接下来p指向h节点的fail指针指向的节点,也就是root;p=p->fail也就是p=NULL说明匹配序列为空,则把节点e的fail指针指向root表示没有匹配序列,对应图-2中的(3),然后节点e进入队列;第3次循环时,弹出的第一个节点a的操作与上一步操作的节点e相同,把a的fail指针指向root,对应图-2中的(4),并入队;第4次进入循环时,弹出节点h(图中左边那个),这时操作略有不同。由于p->next[i]!=NULL(root有h这个儿子节点,图中右边那个),这样便把左边那个h节点的失败指针指向右边那个root的儿子节点h,对应图-2中的(5),然后h入队。以此类推:在循环结束后,所有的失败指针就是图-2中的这种形式。


    三、扫描

    构造好Trie和失败指针后,我们就可以对主串进行扫描了。这个过程和KMP算法很类似,但是也有一定的区别,主要是因为AC自动机处理的是多串模式,需要防止遗漏某个单词,所以引入temp指针。

    匹配过程分两种情况:(1)当前字符匹配,表示从当前节点沿着树边有一条路径可以到达目标字符,此时只需沿该路径走向下一个节点继续匹配即可,目标字符串指针移向下个字符继续匹配;(2)当前字符不匹配,则去当前节点失败指针所指向的字符继续匹配,匹配过程随着指针指向root结束。重复这2个过程中的任意一个,直到模式串走到结尾为止。

     对照上图,看一下模式匹配这个详细的流程,其中模式串为yasherhs。对于i=0,1。Trie中没有对应的路径,故不做任何操作;i=2,3,4时,指针p走到左下节点e。因为节点e的count信息为1,所以cnt+1,并且讲节点e的count值设置为-1,表示改单词已经出现过了,防止重复计数,最后temp指向e节点的失败指针所指向的节点继续查找,以此类推,最后temp指向root,退出while循环,这个过程中count增加了2。表示找到了2个单词she和he。当i=5时,程序进入第5行,p指向其失败指针的节点,也就是右边那个e节点,随后在第6行指向r节点,r节点的count值为1,从而count+1,循环直到temp指向root为止。最后i=6,7时,找不到任何匹配,匹配过程结束。


    到此,AC自动机入门知识就讲完了。HDU 2222入门题必须果断A掉,反正我是参考别人代码敲的。。。

    AC自动机貌似还有很多需要优化的地方,等把基础搞定之后再学习一下怎么优化吧。。

    模板在我的后面一篇博客,也就是hdu2222入门题。

    展开全文
  • AC自动机

    2018-10-09 19:11:37
    要学会AC自动机,首先必须知道什么是Trie树。 ——倪芭·沃锁德 目录 一.概述 二.构造 三.实例 一.概述 Aho-Corasick automaton,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。 一个常见的...
  • AC自动机总结

    万次阅读 多人点赞 2015-08-18 10:00:48
    AC自动机总结 0.引言:  由于大连现场赛的一道 AC自动机+ DP的题目(zoj3545 Rescue the Rabbit)被小媛同学推荐看 AC自动机。经过一段时间的努力,终于把 shǎ崽神牛的 AC自动机专辑题目 AK(其实还差那个高中题。...
  • AC自动机算法

    万次阅读 多人点赞 2011-11-23 09:04:50
    AC自动机简介:  首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有...
  • C语言实现,效率极高,实现了中文的关键字匹配,输出的格式为偏移量加上关键字(中文编码为GB2312)
  • AC自动机详细讲解

    千次阅读 2017-08-20 19:09:00
    AC自动机详细讲解
  • ac自动机java版

    2020-07-30 23:32:25
    从别的共享资源下载的java版ac自动机,已验证使用非常好。
  • AC自动机算法小结

    千次阅读 2015-04-27 20:57:59
    AC自动机,可惜不能自动AC 转载:飘过的小牛   OIer55242 简介 Aho-Corasick automation 该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的...
1 2 3 4 5 ... 20
收藏数 18,469
精华内容 7,387
关键字:

ac自动机