IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> AC自动机 -> 正文阅读

[数据结构与算法]AC自动机


为什么需要AC自动机

对于一个很长的文章或者字符串str,其中有若干个敏感词。
如何找出str中的敏感词呢?

可行的办法是遍历str,然后每到一个位置就与所有敏感词匹配一遍,如果都匹配失败,再回到一开始匹配位置的下一个位置,依次往后。直到当将str遍历完。

但是这种方法太废时间了,如果敏感词的总长度是M,str的长度是N,很明显时间复杂度来到了O(MN)。

AC自动机就是用来高效解决这个问题的。


AC自动机的概念

AC自动机的基础是Trie树(前缀树)。和Trie树不同的是,树中的每个结点除了有指向孩子的指针,还有一个fail指针。

  1. 每个节点都有fail指针,并且根节点fail指针指向空
  2. 根节点下面第一层的孩子的fail指针全部指向根节点
  3. 其他位置的fail指针首先看父亲节点的fail指针有没有到自己的这条路如果有则让当前位置的fail指针指向父亲fail指针所指向的节点,如果没有这条路则通过fail指针继续往上走,如果走到空了,则让fail指针指向根节点
  4. fail指针的含义:如果必须以当前字符结尾形成的路径为str,剩下哪一个字符串的前缀和str的后缀,拥有最大的匹配长度。fail指针就指向那个字符串所对应的节点位置。

在这里插入图片描述

我们如何收集匹配出来的敏感词?

每条路径的结尾必须放一个标志位表示该节点已经走到头了,只要走到头就说明匹配成功。并且还要有一个bool类型的变量表示这个敏感词已经被找到了,下次就不用找这个敏感词了。

每来到一个位置跟着fail指针走一圈,看到的位置有没有走到头,没有就继续匹配。
还是上面的例子:
在这里插入图片描述

如何建立fail指针

使用宽度优先遍历,在弹出一个节点cur时,找cur的下一级节点next,根据cur的fail指向的节点的下一个位置是否是next,修改next的fail指针指向的位置,如果不是就指root。


代码

#include<vector>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
struct Node {
	//表式这个字符串之前有没有加入过答案
	//如果已经加入了,下次匹配到就不需要加入答案了
	bool endUse;
	Node* fail;
	vector<Node*>nexts;
	//如果end不为空则表示某个字符串的结尾
	string end;
	Node()
		:endUse(false)
		, fail(nullptr)
		, nexts(26)
		, end("")
	{}
};
class ACAutomation {
public:
	ACAutomation()
	{
		//初始化一个根节点
		_root = new Node;
	}
	//和前缀树操作一样,只建前缀树
	void insert(const string& str) 
	{
		Node* cur = _root;
		int index = 0;
		for (int i = 0; i < str.size(); i++) {
			index = str[i] - 'a';
			if (cur->nexts[index] == nullptr) 
			{
				cur->nexts[index] = new Node;
			}
			cur = cur->nexts[index];
		}
		cur->end = str;
	}
	//连接fail指针
	void build() 
	{
		//宽度优先遍历
		queue<Node*>q;
		q.push(_root);
		Node* cur = nullptr;
		Node* cfail = nullptr;
		while (!q.empty()) 
		{
			//父亲出队列设置孩子的fail指针
			cur = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) 
			{
				//设置cur->nexts[i]的fail指针
				if (cur->nexts[i]!=nullptr) 
				{
					cur->nexts[i]->fail = _root;//先默认指向根节点,后面如果找到了就重新改
					//找cur节点的fail指针指向的位置
					cfail = cur->fail;
					//寻找cfail指针的要指向的位置
					while (cfail)
					{
						//找到了,并修改位置
						if (cfail->nexts[i]) 
						{
							cur->nexts[i]->fail = cfail->nexts[i];
							break;
						}
						//如果没有,就往上一层fail走,一直走到空,说明走到了根节点
						cfail = cfail->fail;
					}
				}
				q.push(cur->nexts[i]);
			}
		}
	}
	//给一个长字符串content,将其中的敏感词都返回
	vector<string>containWords(const string& content) 
	{
		Node* cur = _root;
		Node* follow = nullptr;
		vector<string>ans;
		int index = 0;
		for (int i = 0; i < content.size(); i++) 
		{
			index = content[i] - 'a';
			//当前字符在这条路上没有配出来,就随着fail指针找另一条路径进行匹配
			while (cur->nexts[index] == nullptr && cur != _root) 
			{
				cur = cur->fail;
			}
			//现在来到的路径是可以继续匹配的
			//现在来到的节点就是前缀树的根节点
			cur = cur->nexts[index] != nullptr ? cur->nexts[index] : _root;
			//来到任何一个节点顺着fail指针走一圈
			follow = cur;
			while (follow != _root) 
			{
				//已经使用过了防止重复收集
				if (follow->endUse) 
				{
					break;
				}
				//找到了
				if (follow->end != "") 
				{
					ans.push_back(follow->end);
					follow->endUse = true;
				}
				follow = follow->fail;
			}
		}
		return ans;
	}
private:
	Node* _root;
};

在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:21:39 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 21:09:29-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码