021（Keywords Search）（AC自动机）

题目：http://ybt.ssoier.cn:8088/problem_show.php?pid=1479

题目思路：一道AC自动机的模板题

备注：还不会字典树和KMP的尽早回去重修

如果让你在一篇文章里找一个单词是否出现，你会怎么做？

爆了他吗？可以，不过KMP比较省时间

然后就有人提出来了“找一堆单词”的想法
爆了他？怎么爆？弄数组吗？但是把单词存进数组里很麻烦

于是，字典树应运而生，把单词搞进树里，操作简单省时间，公共的前缀又将空间复杂度简化，实属不可多得

但这还不够，时间复杂度依旧未曾整理好，每一个单词的成功搜索都代表着新一轮字典树的重修，从根再向上爬实在是费时费力

于是有人提出了这么一个问题：能不能把字典树和KMP有机结合起来？

当我把一个单词搜干净或是确定它搜不成的时候，我就可以不往根去，而是去找另一个节点玩

那这另一个节点，我要保证他再搜索那个单词的时候就已经把这个节点和这个节点之前连着的东西找干净了，如下：

A B B H F V U D N H G B H G Y D

H G B H G Y D

所以你发现了什么吗？从根到这个节点组成的字符串，是我搜索的那个单词的后缀

那么靠着这个，我们可以得出2条原则：

1.这个单词结束后，我去的节点的深度一定不比我结束时所在的节点深，也就是我去的节点到根的距离小于等于这个节点到根的距离

不然就会出现“一个长为5的单词是一个长为4的单词的后缀”，这是什么J*B玩意

2.在保证1的情况下，这个深度要尽量的大，越大越省事

有了这两条原则，我们就可以愉快地写数组了

重新声明，Fail[i] 存的是当这个单词在 i 处结束（或是匹配成功或是失配）它会转移到 Fail[i] ，以后简称为 j 。

开始搜索：

首先，从根上分下来的第一个东西的 j 一定会往根上跑

一是它不可能有数值相同的对家，二是比它深度小的也就只有根了

然后对于后面有着两重可能

一是如果我们当前搜索的节点有儿子，那么 Fail[儿子] 就指向 Fail[它爹] 的节点与儿子数值相同的儿子

然后把这个儿子存起来，当做以后我们要搜索的节点

就算那个“数值相同的儿子”是 0 也没关系，我们让它当跳板，再往回跑就可以了

二是如果没有，就把 Fail[它爹] 的节点的数值相同的儿子指过去就可以

这个“指过去”充当了一个跳板的作用，毕竟还有一堆节点找“它爹”呢，没个儿子给他们指也就说不过去

自此，全部清零

最后一个问题：怎么计数

给每个单词的末尾加个1就可以，碰上了就加一下。

#include<bits/stdc++.h>

using namespace std;

int T,n,tot=0;

string s;

int trie[500010][26],answ[100010],nexT[500010];

//树，单词末尾计数和fail(这里起名字用的是nexT)

void putin(string s){

	int p=0,l=s.size();

	for(int i=0;i<l;++i){

		int id=s[i]-'a';

		if(!trie[p][id]){

			trie[p][id]=++tot;

		}

		p=trie[p][id];

	}//家常便饭的字典树

	answ[p]++;

	//计数

}

void hnext(){

	queue<int> q;

	//由于节点过多，整个队列会方便些

	//对第一层特殊处理

	for(int i=0;i<26;++i){

		int g=trie[0][i];//一个一个来

		if(g){//如果有东西

			nexT[g]=0;//往回指根

			q.push(g);//存起来

		}

		//如果没有就不用管了

	}

	while(!q.empty()){//保证有节点可搜

		int t=q.front();//找到

		q.pop();//扔掉

		for(int i=0;i<26;++i){

			int g=trie[t][i];

			//g是当前节点的儿子

			if(g){//有东西

				q.push(g);//存起来

				nexT[g]=trie[nexT[t]][i];

				//儿子指儿子

			}

			else{//如果没有

				trie[t][i]=trie[nexT[t]][i];

				//也要指一下当跳板

				//但不要再存了

			}

		}

	}

}

int found(string s){

	int ans=0,p=0,l=s.size();

	for(int i=0;i<l;++i){

		int id=s[i]-'a';

		p=trie[p][id];

		for(int j=p;j&&answ[j]!=-1;j=nexT[j]){

			//适配或失配则回去

			ans=ans+answ[j];

			//慢慢加

			answ[j]=-1;

			//搜到了就不要再搜了

		}

	}

	return ans;

}

int main(){

	scanf("%d",&T);

	while(T--){

		memset(trie,0,sizeof(trie));

		memset(answ,0,sizeof(answ));

		memset(nexT,0,sizeof(nexT));

		tot=0;

		scanf("%d",&n);

		for(int i=1;i<=n;++i){

			cin>>s;

			putin(s);

		}

		hnext();

		cin>>s;

		printf("%d\n",found(s));

	}

	return 0;

}

巴特西

021（Keywords Search）（AC自动机）

最新文章

热门文章