一份好用(大雾)的Aho-Corasick自动机模板

hhw posted @ 2014年8月11日 15:25 in 代码 with tags 代码 模板 , 1478 阅读

在ljoj上发现了一道AC自动机模板题,于是就学习了一下,顺便自己写了个模板,感觉工作还算正常,就是长了点,而且没有补边,不过自己用用够了

代码如下:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct mjj{int end,son[30],dad,fail;char c;}trie[300001];
int n;
char dc[100001],wz[1000001];
int tp=1;
queue<int> q;
long long cnt=0;
void ins(int cur,int b,int e)
{
	if(b==e){trie[cur].end=1;return;}
	if(trie[cur].son[dc[b]-'a']==0)
	{
		tp++;
		trie[cur].son[dc[b]-'a']=tp;
		trie[tp].end=0;
		trie[tp].dad=cur;
		trie[tp].c=dc[b];
	}
	ins(trie[cur].son[dc[b]-'a'],b+1,e);
}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	memset(trie,0,sizeof(trie));
	trie[1].end=0;
	trie[1].fail=0;
	trie[1].dad=0;
	for(i=1;i<=n;i++){scanf("%s",dc);ins(1,0,strlen(dc));}
	q.push(1);
	while(!q.empty())
	{
		for(i=0;i<='z'-'a';i++)if(trie[q.front()].son[i]!=0)
		{
			int t=trie[q.front()].son[i];
			int tt=trie[trie[t].dad].fail;
			while(tt!=0&&trie[tt].son[i]==0)tt=trie[tt].fail;
			if(tt==0)trie[t].fail=1;else trie[t].fail=trie[tt].son[i];
			q.push(t);
		}
		q.pop();
	}
	scanf("%s",wz);
	int l=strlen(wz);
	int p=1;
	for(i=0;i<l;i++)
	{
		while(p>1&&trie[p].son[wz[i]-'a']==0)p=trie[p].fail;
		if(trie[p].son[wz[i]-'a'])p=trie[p].son[wz[i]-'a'];
		int tmp=p;
		while(tmp!=1){if(trie[tmp].end==1)cnt++;tmp=trie[tmp].fail;}
	}
	printf("%d\n",cnt);
	return 0;
}
				
Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月08日 01:31

Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign. 123movies

Avatar_small
jackjohnny 说:
2021年8月16日 23:02

I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. solarmovies

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月17日 14:05

This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post.! 먹튀검증

Avatar_small
jackjohnny 说:
2021年8月18日 16:26

We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work. 123movies

Avatar_small
jackjohnny 说:
2021年8月18日 20:56

Great article with excellent idea!Thank you for such a valuable article. I really appreciate for this great information.. know more

Avatar_small
jackjohnny 说:
2021年8月19日 20:52

Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too. soap2day.com

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月20日 18:09

I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. Aesthetic equipment

Avatar_small
jackjohnny 说:
2021年8月23日 16:31

Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. thong tac cong ba dinh

Avatar_small
jackjohnny 说:
2021年8月23日 21:45

This is my first time visit to your blog and I am very interested in the articles that you serve. Provide enough knowledge for me. Thank you for sharing useful and don't forget, keep sharing useful info: smm panel template

Avatar_small
seoservise 说:
2021年8月24日 15:59

Pretty good post. I have just stumbled upon your blog and enjoyed reading your blog posts very much. I am looking for new posts to get more precious info. Big thanks for the useful info. buy Dentitox Pro

Avatar_small
Pune Call Girls 说:
2021年8月25日 18:22

Thank you for such a well written article. It’s full of insightful information and entertaining descriptions. Your point of view is the best among many.

Avatar_small
jackjohnny 说:
2021年8月28日 20:30

I was reading some of your content on this website and I conceive this internet site is really informative ! Keep on putting up. matka

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月29日 23:47

Thank you for another great article. Where else could anyone get that kind of information in such a perfect way of writing? I have a presentation next week, and I am on the look for such information. binary options signals software

Avatar_small
mega888 apk download 说:
2021年8月30日 00:15

This is very interesting content! I have thoroughly enjoyed reading your points and have come to the conclusion that you are right about many of them. You are great.

Avatar_small
لی ویوسوہ ہو یار 说:
2021年8月30日 03:32

I am unable to read articles online very often, but I’m glad I did today. This is very well written and your points are well-expressed. Please, don’t ever stop writing. Newest Search Engines

Avatar_small
jackjohnny 说:
2021年8月30日 19:53

Wonderful blog! I found it while surfing around on Yahoo News. Do you have any suggestions on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Appreciate it. matka tips

Avatar_small
jackjohnny 说:
2021年8月31日 23:34

I haven’t any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. indian satta

Avatar_small
jackjohnny 说:
2021年9月04日 16:36

Thank you for another great article. Where else could anyone get that kind of information in such a perfect way of writing? I have a presentation next week, and I am on the look for such information. kalyan matka

Avatar_small
jackjohnny 说:
2021年9月05日 20:35

I found your this post while searching for some related information on blog search...Its a good post..keep posting and update the information. voyance par tel

Avatar_small
insurance-companies- 说:
2021年9月06日 22:07

Wow, What an exceptional pronounce. i found this too much informatics. it’s miles what i used to be searching for for. i’d as soon as to area you that absorb keep sharing such kind of data.If realistic, thank you.

Avatar_small
jackjohnny 说:
2021年9月06日 22:47

Thank you so much for sharing this great blog.Very inspiring and helpful too.Hope you continue to share more of your ideas.I will definitely love to read. water based PU

Avatar_small
jackjohnny 说:
2021年9月08日 17:47

Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. Coffee

Avatar_small
seoservise 说:
2021年9月08日 21:46

Very useful info. Hope to see more posts soon!. 250 dofollow blog comments

Avatar_small
jackjohnny 说:
2021年9月11日 21:55

Great survey, I'm sure you're getting a great response. 바둑이게임

Avatar_small
matka satta 说:
2021年9月12日 14:43

I was very impressed by this post, this site has always been pleasant news Thank you very much for such an interesting post, and I meet them more often then I visited this site

Avatar_small
matka result 说:
2021年9月13日 18:08

I guess I am not the only one having all the enjoyment here! keep up the good work...

Avatar_small
seoservise 说:
2021年9月14日 20:49 Attractive, post. I just stumbled upon your weblog and wanted to say that I have liked browsing your blog posts. After all, I will surely subscribe to your feed, and I hope you will write again soon! mi pagina web
Avatar_small
jackjohnny 说:
2021年9月14日 22:51

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. เสือมังกร ออนไลน์

Avatar_small
golden matka 说:
2021年9月15日 16:31

This is highly informatics, crisp and clear. I think that everything has been described in systematic manner so that reader could get maximum information and learn many things.

Avatar_small
krogerfeedback 说:
2021年9月18日 23:57

That is a nice hard article.i am stunning a lot appreciative taking into account your best take steps.You positioned absolutely very malleable sponsorship. hold it occurring. hold running a blog. seeking to reading your neighboring book.

Avatar_small
jackjohnny 说:
2021年9月21日 20:22

Thank you very much for this great post. 먹튀폴리스

Avatar_small
Satta king 说:
2021年9月25日 05:24

This is exciting, nevertheless it is vital for you to visit this specific url:

Avatar_small
satta matka 说:
2021年9月26日 18:22

thanks for the tips and information..i really appreciate it..

Avatar_small
sattamatka 说:
2021年9月28日 18:55

Wow, What an exceptional pronounce. i found this too much informatics. it’s miles what i used to be searching for for. i’d as soon as to area you that absorb keep sharing such kind of data.If realistic, thank you.

Avatar_small
satta 说:
2021年9月30日 15:14

i am until the call off of time greatly surprised by means of the amount of recommend understandable in financial credit score to this situation. What you presented became ably researched and adroitly worded in an effort to collect your stand within the location of this across to every and the entire single one one your readers.

Avatar_small
matka 说:
2021年10月02日 19:04

Nice blog, I will keep visiting this blog very often.

Avatar_small
Greatpeople me 说:
2021年10月02日 23:32

This is a brilliant blog! I'm very happy with the comments!..

Avatar_small
krogerexperiencee fu 说:
2021年10月02日 23:47

Great post, please keep on sharing amazing article like this! It makes me happy reading your post

Avatar_small
www.locationsnearmen 说:
2021年10月04日 19:03

You have a good point here!I totally agree with what you have said!!Thanks for sharing your views...hope more people will read this article!!

Avatar_small
jackjohnny 说:
2021年10月04日 21:40

Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. voyance sans attendre

Avatar_small
Digital Ali 说:
2021年10月08日 15:21

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. cheap transcription services

Avatar_small
Digital Ali 说:
2021年10月09日 19:10

I have read a few of the articles on your website now, and I really like your style of blogging. I added it to my favorites blog site list and will be checking back soon. Please check out my site as well and let me know what you think. คาสิโนออนไลน์ฟรีเงิน

Avatar_small
seoservise 说:
2021年10月10日 16:56

i am for the first time here. I found this board and I in finding It truly helpful & it helped me out a lot. I hope to present something back and help others such as you helped me. 검증사이트

Avatar_small
Digital Ali 说:
2021年10月11日 12:41

Great post, and great website. Thanks for the information! spiderman last stand suit

Avatar_small
link 说:
2021年10月12日 18:59

Wow! Such an amazing and helpful post this is. I really really love it. It's so good and so awesome. I am just amazed. I hope that you continue to do your work like this in the future also North American Bancard ISO Program

Avatar_small
talktowendys 说:
2021年10月18日 15:03

The reference you've got published is absolutely beneficial. The sites you have referred turned into pleasing. thank you for sharing.

Avatar_small
seoservise 说:
2021年10月26日 02:52

All the contents you mentioned in post is too good and can be very useful. I will keep it in mind, thanks for sharing the information keep updating, looking forward for more posts.Thanks voyance telephone

Avatar_small
Digital Ali 说:
2021年10月27日 13:52

I am impressed. I don't think Ive met anyone who knows as much about this subject as you do. You are truly well informed and very intelligent. You wrote something that people could understand and made the subject intriguing for everyone. Really, great blog you have got here. bike for teenage girl

Avatar_small
印度签证 说:
2021年11月13日 19:32

Thank you a bunch for sharing this with all of us you actually realize what you are talking about! Bookmarked. Please also seek advice from my site. We could have a hyperlink change contract between us!

Avatar_small
wedding video exampl 说:
2021年11月20日 17:54

thanks due to the fact you have been precise-natured to percentage opinion subsequent to us. we are able to continually recognize all you have finished here because I understand you are selected worried thinking about our.

Avatar_small
ΕΤΑ του Καναδά 说:
2021年11月28日 22:50

The first phase the preparation should, theoretically, be uninfluenced by the intended intensity and duration of the sound which is subsequently produced. In fact, however, so quickly are the three phases accomplished that the pianist rarely has capacity to think, in performance, of each phase separately.

Avatar_small
Liwovosa 说:
2021年12月22日 15:24

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!!! 먹튀검증

Avatar_small
Liwovosa 说:
2021年12月27日 20:12 This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. https://scalar.usc.edu/works/office365-login/outlook-365.html
Avatar_small
Liwovosa 说:
2021年12月29日 15:57

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work! 안전놀이터

Avatar_small
Liwovosa 说:
2022年1月02日 15:39

In the world of www, there are countless blogs. But believe me, this blog has all the perfection that makes it unique in all. I will be back again and again. Farmhouse near chennai


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter