AC自动机

wangyuzhe 蒟蒻 2023-03-16 22:26:19 2

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

You can't use 'macro parameter character #' in math mode# 花 费 5 3 分 2 2 秒 整 理 , 累 死 了

{{ vote && vote.total.up }}

共 1 条回复

root 站长

棒~hh