Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。
要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计#### 和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
中文名 AC自动机
外文名 Aho-Corasick automaton
性质 多模匹配算法
产生时间 1973年
产生地 贝尔实验室
应用
一个常见的例子就是给出个单词，再给出一段包含个字符的文章，让你找出有多少个单词在文章里出现过。 要搞懂自动机，先得有模式树（字典树）和模式匹配算法的基础知识。 自动机算法分为三步：构造一棵树，构造失败指针和模式匹配过程。 如果你对算法了解的话，应该知道算法中的函数函数或者函数是干什么用的。 中我们用两个指针和分别表示，与完全相等。 也就是说，是不断增加的，随着的增加相应地变化，且满足以结尾的长度为j的字符串正好匹配串的前个字符，当 ，的策略是调整的位置（减小值）使得与保持匹配且新的恰好与匹配，而 函数恰恰记录了这个应该调整到的位置。 同样自动机的失败指针具有同样的功能，也就是说当我们的模式串在上进行匹配时，如果与当前节点的关键字不能继续匹配，就应该去当前节点的失>> 败指针所指向的节点继续进行匹配。
英文原文
Problem Description
In the modern time, Search engine came into the life of everybody. Wiskey also wants to bring this feature to his image retrieval system. Every image have a long description, when users type some keywords to find the image, the system will match the keywords >with description of image and show the image which the most keywords be matched. To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will >be match.
Input
The last line is the description, and the length will be not longer than1000000.
Output
Print how many keywords are contained in the description.
中文翻译
问题描述
在近代，搜索引擎进入了每个人的生活，也希望将此功能引入他的图像检索系统中。每个图像都有很长的描述，当用户键入一些关键字来查找图像时，系统>会匹配这些关键字并附有图片说明，并显示匹配关键字最多的图片。为了简化问题，给您一个图像描述和一些关键字，您应该告诉我要匹配多少个关键字。
输入
最后一行是说明，长度不得超过。
输出
打印说明中包含多少个关键字。
自动机 C++ 源代码
#include <iostream>
#include <cstring>
using namespace std;
const int kind = 26;
struct node {
node *fail;//失败指针
node *next[kind];//Trie每个节点的26个子节点（最多26个字母）
int count;//是否为该单词的最后一个节点
node() { //构造函数初始化
fail = NULL;
count = 0;
memset(next, NULL, sizeof(next));
}
} *q[1000000];//队列，方便用于bfs构造失败指针
char keyword[51];//输入的单词
char str[1000001];//模式串
共 5 条回复
你整理的啥？
e,我忘写main了
报错了
em^
花 费 5 3 分 2 2 秒 整 理 ， 累 死 了