相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3940
解题报告
用栈和AC自动机来模拟即可
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int SGZ = 26; char ctn[N], wrd[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } class AC_Automaton{ int Root, cnt, ch[N][SGZ], apt[N], dep[N], fail[N]; queue<int> que; public: inline void insert(char *s, int len) { int w = Root; for (int i = 1; i <= len; i++) { int cc = s[i] - 'a'; if (!ch[w][cc]) { ch[w][cc] = ++cnt; dep[cnt] = dep[w] + 1; } w = ch[w][cc]; } apt[w] = len; } inline void build() { for (int i = 0; i < SGZ; i++) { if (ch[Root][i]) { que.push(ch[Root][i]); } } for (; !que.empty(); que.pop()) { int w = que.front(); for (int i = 0; i < SGZ; i++) { if (ch[w][i]) { fail[ch[w][i]] = ch[fail[w]][i]; apt[ch[w][i]] = max(apt[ch[w][i]], apt[fail[ch[w][i]]]); que.push(ch[w][i]); } else { ch[w][i] = ch[fail[w]][i]; } } } } inline int root() { return Root; } inline int move(int &w, int cc) { w = ch[w][cc]; return apt[w]; } }aca; int main() { scanf("%s", ctn + 1); int n = read(), m = strlen(ctn + 1); for (int i = 1; i <= n; i++) { scanf("%s", wrd + 1); aca.insert(wrd, strlen(wrd + 1)); } aca.build(); vector<int> ans, pos; for (int i = 1; i <= m; i++) { int w = pos.empty()? aca.root(): *--pos.end(); int len = aca.move(w, ctn[i] - 'a'); ans.push_back(ctn[i]); pos.push_back(w); for (int j = 1; j <= len; j++) { ans.pop_back(); pos.pop_back(); } } for (int i = 0; i < (int)ans.size(); i++) { putchar(char(ans[i])); } return 0; }
I loved your article post.Really looking forward to read more.
Thank you ever so for you post.Really thank you! Great.
Looking forward to reading more. Great blog. Awesome.
Major thanks for the article post. Much obliged.
Thanks again for the blog.Really looking forward to read more. Want more.
A round of applause for your blog post.Really thank you! Want more.
A round of applause for your article post.Much thanks again. Cool.
Very informative post.Thanks Again. Much obliged.
Thanks for the blog article.Much thanks again. Fantastic.
Major thanks for the post. Great.
Great blog. Will read on…
Thanks again for the blog post.Thanks Again. Really Great.
Thanks-a-mundo for the article. Really Great.
A round of applause for your post.Much thanks again.
Major thankies for the article post.Really looking forward to read more. Really Cool.
Really enjoyed this article.Thanks Again. Really Great.
I appreciate you sharing this blog.Really looking forward to read more. Really Great.
Im obliged for the article.Much thanks again.
I appreciate you sharing this article post.Much thanks again. Really Great.
Fantastic article.Thanks Again. Keep writing.
Im thankful for the article post.Really looking forward to read more. Really Cool.
I loved your article.Really thank you! Cool.
wow, awesome blog post. Much obliged.
Thanks a lot for the article.Much thanks again. Keep writing.
A round of applause for your blog article.Really looking forward to read more. Want more.
I really liked your blog.Really thank you! Great.
I was able to find good information from your blog articles.
Really informative blog post.Thanks Again. Will read on…
A round of applause for your blog article. Want more.
Usually I don’t read article on blogs, however I would like to say that this write-up very pressured me to check out and do so!
Your writing taste has been amazed me. Thank you, very
great post.
Very informative article.Thanks Again.
I think this is a real great post. Great.
Thanks for the blog article.Thanks Again. Much obliged.
Awesome blog.Really looking forward to read more. Great.
Really informative blog article.Really thank you! Awesome.
I value the blog post.Really looking forward to read more. Keep writing.
Hello! I’ve been reading your website for a while now and finally got the bravery to go ahead and
give you a shout out from Austin Tx! Just wanted to say keep up the excellent work!
Im grateful for the post.Really thank you! Cool.
Im thankful for the article post.Thanks Again. Want more.
I cannot thank you enough for the blog.Thanks Again. Really Great.
You’ve made some really good points there. I looked on the net for
more information about the issue and found most
people will go along with your views on this
web site.
Thanks again for the article post.Much thanks again. Really Cool.
Thanks so much for the article post.Much thanks again. Much obliged.
You made some good points there. I checked on the
internet to find out more about the issue and found most individuals will go along with your views on this site.
Awesome blog.Really looking forward to read more. Really Great.
I value the article.Really thank you! Really Great.
Thanks a lot for sharing this with all folks you really recognize what you are talking about!
Bookmarked. Please additionally visit my website =).
We will have a link trade contract among us
Wow, great post.Much thanks again. Awesome.
Thanks-a-mundo for the article post.Really thank you! Cool.
Thanks so much for the article.Really looking forward to read more. Will read on…
Thanks for sharing, this is a fantastic article post. Really Great.
Say, you got a nice blog post. Great.
Im obliged for the blog post.Really thank you! Really Cool.
Great post.Thanks Again. Cool.
Muchos Gracias for your article.Really thank you! Will read on…
Really appreciate you sharing this blog article.Thanks Again. Really Great.
Thanks again for the blog post.Really thank you!
Muchos Gracias for your article.Much thanks again. Will read on…
Really appreciate you sharing this blog.Really thank you! Much obliged.
Thanks so much for the post.Much thanks again. Want more.
A round of applause for your blog article.Thanks Again.
You made some really good points there. I looked on the web to
learn more about the issue and found most individuals will go along with your views
on this web site.
Im thankful for the article post.Much thanks again. Awesome.
Very good blog post.Much thanks again. Cool.
Im thankful for the blog post.Really looking forward to read more. Really Cool.
Thanks-a-mundo for the blog post. Fantastic.
Major thankies for the article. Great.
What’s up everyone, it’s my first pay a quick visit at this website, and post is truly fruitful designed for me,
keep up posting such articles or reviews.
wow, awesome blog post. Want more.
I constantly spent my half an hour to read this website’s articles everyday along with a mug of
coffee.
I appreciate you sharing this article.Really thank you! Will read on…
Thanks for sharing, this is a fantastic blog. Awesome.
Enjoyed every bit of your post.Really looking forward to read more. Much obliged.
Thanks so much for the article post. Awesome.
Really appreciate you sharing this blog.Really thank you! Keep writing.
I am delighted that I detected this website, precisely the right info that I was searching for! .
Thanks-a-mundo for the blog post.Really thank you! Really Great.
Please let me know if you’re looking for a writer for your site.
You have some really good articles and I feel I would be a good asset.
If you ever want to take some of the load off, I’d absolutely love to write some articles for your
blog in exchange for a link back to mine. Please shoot me an e-mail
if interested. Cheers!
Really informative post.Much thanks again. Want more.
I am so grateful for your blog article.Really looking forward to read more. Want more.
Major thankies for the article.Really thank you! Fantastic.
I really liked your article.Really looking forward to read more. Will read on…
Thanks-a-mundo for the post. Fantastic.
Awesome article post.Much thanks again. Keep writing.
I appreciate you sharing this article post.Really thank you! Cool.
Very informative article.Much thanks again. Much obliged.
Muchos Gracias for your article post.Much thanks again. Want more.
I am so grateful for your article post.Really thank you! Much obliged.
I cannot thank you enough for the article. Cool.
Very good blog.Much thanks again. Want more.
Appreciate you sharing, great article.Thanks Again. Really Cool.
Really informative post.Much thanks again. Really Cool.
Thanks a lot for the blog post. Great.
I think this is a real great blog.Much thanks again. Much obliged.
Very good blog article.Thanks Again. Great.
I really liked your post.Much thanks again. Great.
Thanks for the article.Really thank you! Fantastic.
Awesome article post.Really thank you! Cool.
Very good article post.Really looking forward to read more. Really Great.
I really like and appreciate your blog.Thanks Again. Keep writing.
Im obliged for the blog article. Awesome.
Thanks for sharing, this is a fantastic blog.Thanks Again. Will read on…
Looking forward to reading more. Great blog.Really thank you!
You are really a good webmaster, you have done a well job on this topic!
I think this is a real great blog article.Much thanks again. Cool.
Spot on with this write-up, I honestly believe that this web site needs much more attention. I’ll probably be back again to see more, thanks for the advice!
This is one awesome article post.Much thanks again. Cool.
Very neat blog.Much thanks again. Fantastic.
Enjoyed every bit of your post.Really thank you! Fantastic.
Enjoyed every bit of your post.Much thanks again. Awesome.
Thanks for sharing, this is a fantastic article post.Really thank you! Cool.
Appreciate you sharing, great blog post. Keep writing.
I really like and appreciate your post.Much thanks again. Keep writing.
Muchos Gracias for your article.Thanks Again. Really Great.
Major thankies for the article.Much thanks again. Awesome.
I loved your blog post. Cool.
A big thank you for your article post.Thanks Again. Really Cool.
I cannot thank you enough for the article.Much thanks again. Keep writing.
I enjoy, lead to I found exactly what I used to be looking for.
You have ended my 4 day long hunt! God Bless you man. Have a nice day.
Bye
Very informative article.Much thanks again. Great.
I truly appreciate this blog article.Really looking forward to read more. Much obliged.
Im thankful for the blog.Really looking forward to read more. Will read on…
I think this is a real great blog article.Really looking forward to read more.
Hey, thanks for the post.Much thanks again. Much obliged.
Thanks for sharing, this is a fantastic blog.Really looking forward to read more. Cool.
I really liked your blog post.Much thanks again. Fantastic.
Pretty nice post. I simply stumbled upon your weblog and
wished to mention that I’ve really loved browsing your blog posts.
After all I will be subscribing for your feed and I am hoping you write again very soon!
Muchos Gracias for your blog post. Much obliged.
Appreciate the recommendation. Will try it out.
Appreciate you sharing, great post.Much thanks again. Awesome.
Looking forward to reading more. Great article post.Much thanks again. Fantastic.
Really appreciate you sharing this blog post.Really thank you! Awesome.
Very informative blog.Much thanks again. Much obliged.
Very good article. Much obliged.
Appreciate you sharing, great blog. Really Cool.
This is one awesome post.Thanks Again. Will read on…
Really informative article. Cool.
I really like and appreciate your blog.Thanks Again. Much obliged.
Thank you for your article.Thanks Again.
Great, thanks for sharing this article. Keep writing.
I am so grateful for your blog post.Really thank you! Keep writing.
This is one awesome article post.Really looking forward to read more. Awesome.
I know this if off topic but I’m looking into starting my own blog and was curious what all is needed to get set up?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web smart so I’m not 100% sure. Any tips or advice would be greatly
appreciated. Kudos
Greetings I am so delighted I found your web site, I really found
you by accident, while I was browsing on Digg for
something else, Nonetheless I am here now and would just like to say
kudos for a fantastic post and a all round exciting
blog (I also love the theme/design), I don’t have
time to read through it all at the minute but I have saved it and
also included your RSS feeds, so when I have time I will be back to read a lot more, Please do keep up the great
work.
Major thankies for the post.Really thank you! Great.
wow, awesome article post.Really looking forward to read more. Much obliged.
Wow, great article.Really thank you!
Incredible points. Solid arguments. Keep up the amazing effort.
Really enjoyed this post.Much thanks again. Cool.
Thanks-a-mundo for the blog article.Really thank you! Much obliged.
Fantastic blog.Really thank you! Great.
I value the blog post.Thanks Again. Much obliged.
Thanks again for the post.Much thanks again. Fantastic.
Great, thanks for sharing this article post.Thanks Again. Awesome.
I really liked your article.Thanks Again. Much obliged.
I really like and appreciate your article.Thanks Again. Really Great.
I really liked your article. Cool.
I am so grateful for your article. Will read on…
Looking forward to reading more. Great blog. Great.
Say, you got a nice article post. Fantastic.
Fantastic article post.Thanks Again. Will read on…
Really enjoyed this article post.Really looking forward to read more. Keep writing.
Thanks for the blog.Really thank you! Much obliged.
I am so grateful for your article post.Much thanks again. Cool.
Thanks again for the post.Much thanks again.
Thank you ever so for you article. Fantastic.
Very neat blog.Thanks Again. Will read on…
I am so grateful for your post.Much thanks again. Keep writing.
I cannot thank you enough for the article post.Really looking forward to read more.
Im obliged for the blog post.Much thanks again. Great.
Major thanks for the post.Thanks Again. Want more.
Really informative blog post.Thanks Again. Cool.
Fantastic article post. Great.
I think this is a real great blog.Really looking forward to read more. Great.
A big thank you for your blog.Really looking forward to read more. Great.
Looking forward to reading more. Great blog.Really thank you! Will read on…
I appreciate you sharing this article post.Much thanks again. Really Cool.
I loved your post. Will read on…
Very informative blog post. Will read on…
Thanks for the blog article.Really looking forward to read more. Will read on…
Awesome post.
Thanks-a-mundo for the post.Thanks Again. Really Cool.
A big thank you for your blog.Really thank you! Really Cool.
Thank you ever so for you article. Keep writing.
Awesome blog.Much thanks again. Great.
great put up, very informative. I ponder why the opposite specialists of this sector don’t notice this. You must continue your writing. I am confident, you have a great readers’ base already!
Im grateful for the article post.Thanks Again. Cool.
Wow, incredible blog structure! How long haveyou been running a blog for? you make running a blog glance easy.The overall look of your web site is excellent, let alonethe content!
bii buy cbd oil
Very good blog article.Thanks Again. Much obliged.
Hello! Quick question that’s entirely off topic. Do you know how to make your site mobile friendly? My website looks weird when browsing from my iphone 4. I’m trying to find a theme or plugin that might be able to correct this problem. If you have any suggestions, please share. Thanks!
I cannot thank you enough for the post.Really looking forward to read more. Cool.
You made some clear points there. I looked on the internet for the subject and found most individuals will go along with with your website.
Please leet me know if you’re looking for a article writer for yourweblog. Youu have some really good posts and I believe I wouldbe a good asset. If you ever want to take some of the load off, I’d really like to write skmearticles for your blog in exchange for a link back to mine.Please send me ann email if interested. Thanks!
Really appreciate you sharing this blog article.Thanks Again. Will read on…
I cannot thank you enough for the blog post.Really looking forward to read more. Awesome.
I truly appreciate this post.Really thank you! Really Great.
I loved your article.Really thank you! Awesome.
Thank you ever so for you article.Thanks Again. Really Great.
Thanks so much for the blog post. Fantastic.
Major thankies for the article post. Keep writing.
Really informative article post.Really looking forward to read more.
Hey, thanks for the blog article.Thanks Again. Cool.
cash advance payday loans online cash check short term loans [url=https://zxepersonalloansonlinesmall.com/]payday loans no credit check no employment verification[/url] ’
Thanks-a-mundo for the post.Thanks Again. Fantastic.
I appreciate you sharing this post. Cool.
Im obliged for the article post.Thanks Again.
Enjoyed every bit of your blog post.Really looking forward to read more. Want more.
Hello to all, thhe contents present at this site are iin factawesome for peoplpe knowledge, well, keep up the good work fellows.
I really liked your blog.Thanks Again.
Thank you for your blog article.Really looking forward to read more. Will read on…
Very informative blog.Thanks Again. Cool.
wow, awesome article.Thanks Again.
Great blog post.Thanks Again. Keep writing.
Thank you for your blog article.Thanks Again. Fantastic.
When some one searches for his vital thing, therefore he/she desires to be available that in detail, thus that thing is maintained over here.|
Saved as a favorite, I like your web site!|
Thanks for the article post.Thanks Again. Want more.
This is one awesome post. Will read on…
Thank you for the auspicious writeup. It if truth be told was a leisure account it. Glance advanced to far brought agreeable from you! However, how could we keep in touch?|
Appreciate you sharing, great blog.Really looking forward to read more. Will read on…
Really enjoyed this article post.Thanks Again. Keep writing.
Great, thanks for sharing this blog.Much thanks again. Keep writing.
Very good info. Lucky me I came across your website by chance (stumbleupon). I have bookmarked it for later!|
I cannot thank you enough for the post.Really looking forward to read more.
I really like and appreciate your article.Much thanks again. Keep writing.
I loved your article post. Much obliged.
Im thankful for the article.Really thank you! Awesome.
wow, awesome article.Really looking forward to read more. Great.
Thanks again for the blog post.Really looking forward to read more. Great.
Really informative blog article.Thanks Again. Really Great.
I was recommended this website by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my trouble. You are wonderful! Thanks!
May I just say what a comfort to find somebody that actually understands what they are talking about over the internet. You certainly realize how to bring an issue to light and make it important. A lot more people really need to check this out and understand this side of the story. It’s surprising you are not more popular given that you definitely have the gift.|
Fascinating blog! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple adjustements would really make my blog shine. Please let me know where you got your design. Thanks a lot|
Really appreciate you sharing this article post.Thanks Again. Really Cool.
Very informative article.Really thank you!
Thank you ever so for you article. Cool.
Hey There. I found your blog using msn. That is an extremely neatly written article. I will be sure to bookmark it and come back to read extra of your useful info. Thank you for the post. I’ll definitely return.|
Ahaa, its good dialogue concerning this post here at this web site, I have read all that, so at this time me also commenting at this place.|
obviously like your web-site however you have to check the spelling on several of your posts. Many of them are rife with spelling problems and I to find it very troublesome to inform the truth nevertheless I will certainly come back again.
Whoa! This blog looks just like my old one! It’s on a completely different subject but it has pretty much the same page layout and design. Great choice of colors!|
Thanks again for the blog article.Really looking forward to read more. Fantastic.
Every weekend i used to pay a visit this web site, as i want enjoyment, since this this web site conations actually fastidious funny stuff too.|
Enjoyed every bit of your blog.Much thanks again.
I truly appreciate this blog article. Great.
Really informative article post.Really looking forward to read more. Awesome.
Heya i am for the first time here. I found this board and I find It really useful & it helped me out a lot. I hope to give something back and aid others like you aided me.|
I cannot thank you enough for the blog post.Really thank you! Really Great.
Thank you ever so for you post.Much thanks again. Really Great.
Major thankies for the post.Really thank you! Cool.
I truly appreciate this blog. Keep writing.
I know this if off topic but I’m looking into starting my own weblog and was wondering what all is needed to get setup? I’m assuming having a blog like yours would cost a pretty penny? I’m not very internet savvy so I’m not 100 sure. Any recommendations or advice would be greatly appreciated. Many thanks|
I appreciate you sharing this blog article. Awesome.
Thanks for sharing, this is a fantastic article post.Much thanks again. Really Cool.
It’s genuinely very complex in this busy life to listen news on TV, therefore I simply use web for that reason, and take the latest information.|
You have made some good points there. I checked on the net for more information about the issue and found most people will go along with your views on this website.|
When I originally commented I appear to have clicked the -Notify me when new comments are added- checkbox and now every time a comment is added I recieve 4 emails with the exact same comment. Is there a means you can remove me from that service? Thanks!|