AC自动机

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];//模式串