AC自动机（HDU 2222: Keywords Search）-白红宇

AC自动机（HDU 2222: Keywords Search）

阅读量：2143 次

发布时间：2019-04-30

本文共 1267 字，大约阅读时间需要 4 分钟。

输入n个单词，再输入一篇文章，判断有多少个单词在文章中出现过

注释都在代码里

#include
   
    #include
    
     #include
     
      using namespace std;struct Trie{	int ans, len, x, now, root, i, loc, temp, next[500005][26], fail[500005], sum[500005];	int Newnode()		/*申请新的节点，这个节点的位置是loc*/	{		for(i=0;i<=25;i++)		/*初始化当前节点*/			next[loc][i] = -1;		sum[loc++] = 0;				/*节点申请完毕，当前位置loc已被占用，所以让loc+1以便下次申请*/		return loc-1;		/*返回当前节点位置*/	}	void Init()		/*初始化字典树*/	{		loc = 0;		root = Newnode();	}	void Update(char a[])		/*字典树的更新*/	{		int len = strlen(a);		int now = root;		for(int i=0;i

q; /*fail[k]的作用：文章如果在k节点匹配失败，则可以跳到fail[k]处继续匹配，这个同理KMP的next[]数组*/ fail[root] = root; for(i=0;i<=25;i++) { if(next[root][i]==-1) next[root][i] = root; else { fail[next[root][i]] = root; /*初始化根节点与它的所有子节点的失败指针*/ q.push(next[root][i]); /*根节点与它的所有子节点（位置loc）进入队列*/ } } while(q.empty()==0) /*从字典树的根开始进行广搜*/ { now = q.front(); q.pop(); for(i=0;i<=25;i++) { if(next[now][i]==-1) /*k节点的某个子节点不存在，那么可以跳到fail[k]对应的子节点*/ next[now][i] = next[fail[now]][i]; else { fail[next[now][i]] = next[fail[now]][i]; /*k节点的某个子节点p存在，那么fail[p]就是fail[k]对应相同字符的子节点*/ q.push(next[now][i]); } } } } int Query(char a[]) { ans = 0; len = strlen(a); now = root; for(i=0;i

你可能感兴趣的文章

《kubernetes权威指南·第四版》第二章：kubernetes安装配置指南