题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4567
这个题，就AC自动机搞一搞就可以啦！
省选时的我都能A，这是真简单啊！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define AC AC_Automata
#define LL long long
using namespace std;
LL vout = 0;
char pat[510000+9];
namespace AC_Automata{
const int N = 510000+9;
const int SIGMA_SIZE = 26;
struct Node{int ch[SIGMA_SIZE],fail,last,vis;}p[N];
int cnt,que[N],itr1,itr2;
vector<int> G[N];
int head[N],to[N],nxt[N];
int TOT,tot,sz[N];
inline void AddEdge(int u, int v){to[++TOT] = v; nxt[TOT] = head[u]; head[u] = TOT;}
inline void insert(char *s){
int len = strlen(s), w=0;
for (int i=0;i<len;i++){
int c = s[i] - 'a';
if (!p[w].ch) w = p[w].ch = ++cnt;
else w = p[w].ch;
} p[w].vis++;
}
inline void GetFail(){
itr1 = 0; itr2 = 1;
for (int i=0;i<SIGMA_SIZE;i++)
if (p[0].ch[i]) que[++itr1] = p[0].ch[i];
while (itr2 <= itr1){
int w = que[itr2++];
if (p[w].vis) AddEdge(p[w].last, w);
for (int i=0;i<SIGMA_SIZE;i++){
if (p[w].ch[i]) {
int nw = p[w].fail;
while (nw && !p[nw].ch[i]) nw = p[nw].fail;
p[p[w].ch[i]].fail = p[nw].ch[i];
p[p[w].ch[i]].last = p[p[nw].ch[i]].vis ? p[nw].ch[i] : p[p[nw].ch[i]].last;
que[++itr1] = p[w].ch[i];
}
}
}
}
void DFS(int w){
sz[w] = 1;
for (int i=head[w];i;i=nxt[i]) DFS(to[i]), sz[w] += sz[to[i]], G[w].push_back(sz[to[i]]);
int len = G[w].size();
sort(G[w].begin(), G[w].end());
for (int i=0,sta=0;i<len;i++) vout += (LL)sta + 1LL, sta += (LL)G[w][i];
}
};
int main(){
int n; scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%s",pat), AC::insert(pat);
AC::GetFail(); AC::DFS(0);
printf("%lld",vout);
return 0;
}
Hey There. I found your blog using msn. This is an extremely well written article.
I’ll make sure to bookmark it and return to read more of your
useful info. Thanks for the post. I will definitely comeback.
Magnificent site. A lot of useful information here.
I’m sending it to several pals ans additionally sharing in delicious.
And naturally, thank you for your effort!
Hi there! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations?
This article offers clear idea in support of the new
visitors of blogging, that really how to do blogging and site-building.
This is my first time pay a quick visit at here and i am really pleassant to
read everthing at one place.
If you are going for finest contents like I do, simply go to see this website everyday as
it offers quality contents, thanks
Undeniably believe that which you stated. Your favorite reason seemed to be on the web the easiest thing
to be aware of. I say to you, I definitely get annoyed while people think about worries
that they plainly don’t know about. You managed to
hit the nail upon the top and defined out the whole thing without having side-effects , people could take
a signal. Will probably be back to get more. Thanks
Very soon this web page will be famous among all blog viewers, due to it’s
pleasant articles
fantastic submit, very informative. I wonder why the opposite experts
of this sector do not notice this. You should proceed your writing.
I’m sure, you’ve a great readers’ base already!
Why users still use to read news papers when in this
technological world everything is accessible on web?
You can certainly see your skills in the article you write.
The world hopes for more passionate writers such as
you who are not afraid to say how they believe.
Always follow your heart.
I got this website from my buddy who told me regarding this website and
at the moment this time I am browsing this website
and reading very informative articles at this time.
This is a topic that is close to my heart… Best wishes!
Where are your contact details though?
If you want to obtain a good deal from this article then you have
to apply these techniques to your won website.
Hi Dear, are you actually visiting this site daily, if so after that you will absolutely obtain fastidious experience.
I am really grateful to the owner of this web site who has
shared this impressive article at at this place.
Please let me know if you’re looking for a article writer for your weblog.
You have some really great articles and I think I would be a good asset.
If you ever want to take some of the load off, I’d love
to write some content for your blog in exchange for a link back to mine.
Please send me an e-mail if interested. Regards!
Quality posts is the important to interest the users
to pay a visit the website, that’s what this web page is providing.
I absolutely love your blog.. Very nice colors & theme.
Did you build this amazing site yourself? Please reply back as I’m trying to
create my own site and want to know where you got this from or
what the theme is named. Cheers!
I have been browsing on-line greater than 3 hours
lately, yet I by no means found any interesting article like
yours. It is beautiful price sufficient for me. In my
opinion, if all web owners and bloggers made excellent content as you probably did, the net will likely be much more helpful than ever before.
natalielise plenty of fish
It’s a pity you don’t have a donate button! I’d without a doubt donate to this fantastic blog!
I suppose for now i’ll settle for book-marking and adding your RSS feed to my Google account.
I look forward to fresh updates and will talk about this site with my Facebook group.
Chat soon!
Hi! I understand this is sort of off-topic but I needed to ask.
Does running a well-established website such as yours require a lot of
work? I’m brand new to running a blog but I
do write in my diary on a daily basis. I’d like to start a blog so I can share my experience
and feelings online. Please let me know if you have any suggestions
or tips for brand new aspiring bloggers. Appreciate it!
pof natalielise
Amazing! Its genuinely awesome paragraph, I have got
much clear idea on the topic of from this paragraph.
I read this paragraph completely regarding the comparison of newest and previous technologies, it’s awesome article.
natalielise pof
Having read this I thought it was really enlightening. I appreciate you finding the time
and energy to put this content together. I once again find
myself personally spending a lot of time both reading and
leaving comments. But so what, it was still worth it!
Hi, i read your blog from time to time and i own a similar one and i was
just wondering if you get a lot of spam remarks?
If so how do you reduce it, any plugin or anything you can advise?
I get so much lately it’s driving me mad so any help is very
much appreciated.
Heya i’m for the first time here. I came across this board and I find It truly useful &
it helped me out much. I am hoping to give something
back and aid others like you aided me.
Hi there, i read your blog occasionally and i own a similar one
and i was just wondering if you get a lot of
spam comments? If so how do you reduce it, any plugin or
anything you can advise? I get so much lately it’s driving me insane
so any support is very much appreciated.
Informative article, exactly what I wanted to find.
This is a topic that is close to my heart… Thank you!
Where are your contact details though?
It’s going to be finish of mine day, however before finish I am
reading this impressive article to improve my know-how.
I am no longer certain where you are getting your info, however great topic.
I needs to spend a while learning much more or understanding more.
Thank you for fantastic info I was looking for this info
for my mission.
Hello there, I think your web site may be having web browser compatibility issues.
When I take a look at your blog in Safari, it looks fine but when opening in I.E., it has some overlapping issues.
I simply wanted to give you a quick heads up! Aside from that, excellent site!
I don’t even know how I ended up here, but I
thought this post was good. I don’t know who you are but definitely you
are going to a famous blogger if you aren’t already 😉 Cheers!
For most recent news you have to visit the web and on the web I
found this site as a most excellent site for most recent updates.
Asking questions are in fact pleasant thing if you are not understanding something entirely,
but this piece of writing provides pleasant understanding even.
Thank you for every other informative website.
The place else may just I get that type of information written in such an ideal way?
I have a challenge that I am simply now working on, and I have been at the look out for such information.
It’s remarkable to pay a visit this site and reading the
views of all mates about this piece of writing, while
I am also eager of getting know-how.
I really like what you guys are up too. This type of clever work and exposure!
Keep up the good works guys I’ve incorporated you
guys to blogroll.
Thanks for sharing your thoughts about quest bars cheap.
Regards
Every weekend i used to pay a quick visit this site, as i want
enjoyment, since this this website conations in fact good funny information too.
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now
each time a comment is added I get three emails with the same comment.
Is there any way you can remove people from that service?
Thank you!
Thanks for your personal marvelous posting! I truly enjoyed reading it,
you happen to be a great author.I will be
sure to bookmark your blog and will often come back at some point.
I want to encourage one to continue your great writing, have a nice morning!
Aw, this was a very good post. Spending some time and actual effort to generate a
top notch article… but what can I say… I put things off a whole lot and don’t manage to get
anything done.
ywyozyqhy ijttd nvxkcjf krvw mmrbbxynrbblehj
Hey there, I think your site might be having browser compatibility issues.
When I look at your blog site in Opera, it
looks fine but when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, amazing blog!
Thanks a bunch for sharing this with all folks you actually understand what you’re talking approximately!
Bookmarked. Kindly additionally discuss with my site =).
We will have a link change contract among us
I absolutely love your blog and find a lot of your post’s to be exactly I’m looking for.
can you offer guest writers to write content
for you personally? I wouldn’t mind composing a post or elaborating on some of the subjects you write concerning here.
Again, awesome site!
I used to be able to find good info from your blog articles.
Great article.
What’s up to all, since I am genuinely eager of reading this blog’s post to be updated on a regular basis.
It contains nice stuff.
Ahaa, its good discussion on the topic of this post at
this place at this web site, I have read all that, so now me also
commenting at this place.
That is a really good tip especially to those
new to the blogosphere. Short but very accurate info… Thanks for sharing this one.
A must read article!
Someone essentially help to make critically posts
I’d state. This is the very first time I frequented
your website page and up to now? I surprised with the research you made to make this particular submit extraordinary.
Wonderful job!
This design is steller! You certainly know how to keep a reader amused.
Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
I really loved what you had to say, and more than that, how you
presented it. Too cool!
Good day! This is my first comment here so I just wanted to give a
quick shout out and say I truly enjoy reading
your blog posts. Can you suggest any other blogs/websites/forums that cover the same subjects?
Thanks for your time!
Why users still make use of to read news papers when in this technological world
all is accessible on net?
When someone writes an article he/she retains the image of a user in his/her
mind that how a user can understand it. So that’s why this paragraph is
perfect. Thanks!
I’m gone to tell my little brother, that he should
also visit this weblog on regular basis to get updated from most up-to-date
news.
Hi there to every one, it’s actually a pleasant for me to go
to see this web site, it includes priceless Information.
Excellent article. Keep posting such kind of info on your site.
Im really impressed by your blog.
Hello there, You’ve performed a fantastic job. I will definitely
digg it and individually suggest to my friends.
I am sure they’ll be benefited from this site.
I am sure this piece of writing has touched all the internet visitors, its really really nice paragraph on building up new weblog.
The other day, while I was at work, my cousin stole my apple ipad
and tested to see if it can survive a forty foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is completely off topic but I had to share it with someone!
I’m curious to find out what blog system you’re using?
I’m experiencing some minor security issues with my latest site and
I would like to find something more risk-free.
Do you have any suggestions?
Hi to all, it’s really a fastidious for me to pay a quick visit this website, it consists of priceless Information.
It’s actually a cool and helpful piece of information. I am glad that you just shared this useful info with us.
Please stay us up to date like this. Thanks for sharing.
Definitely consider that which you stated. Your favourite justification seemed to be on the internet the easiest thing to take into account of.
I say to you, I certainly get irked at the same time as people think
about issues that they plainly do not realize
about. You controlled to hit the nail upon the highest and also defined out
the entire thing without having side effect , folks can take
a signal. Will probably be again to get more. Thanks
It’s very easy to find out any matter on net as compared to textbooks, as
I found this piece of writing at this web page.
My family all the time say that I am wasting my time here
at net, except I know I am getting know-how everyday by reading thes
good content.
You really make it seem so easy with your presentation but I find
this topic to be really something that I think I would never understand.
It seems too complicated and very broad for me. I am looking forward for your next post, I will try to get the hang of it!
Hi there! I know this is kind of off topic
but I was wondering which blog platform are you using for this site?
I’m getting tired of WordPress because I’ve had issues with hackers and I’m
looking at options for another platform. I would be awesome if you could point me in the direction of a good platform.
I like this web site so much, saved to bookmarks.
Hi my loved one! I want to say that this article is awesome, nice
written and come with approximately all vital infos. I’d like to see more posts
like this .
I am regular visitor, how are you everybody? This article posted at this website is genuinely pleasant.
For latest news you have to visit web and on web I found this website as a most excellent web
site for newest updates.
Whats up very nice web site!! Guy .. Beautiful .. Amazing ..
I will bookmark your web site and take the feeds also?
I am happy to seek out numerous helpful info
here within the submit, we’d like work out extra strategies on this regard, thank you for
sharing. . . . . .
Very nice post. I simply stumbled upon your weblog and wished to mention that
I have really enjoyed surfing around your weblog posts. In any case I will be subscribing for your rss feed and I am hoping you write once more very soon!
Hello there! This is my 1st comment here so I just wanted to give a quick shout out and say I genuinely enjoy reading your
articles. Can you recommend any other blogs/websites/forums that cover the same subjects?
Thanks a lot!
Pretty section of content. I just stumbled upon your web site and in accession capital to assert that I acquire actually enjoyed
account your blog posts. Any way I’ll be subscribing to your
feeds and even I achievement you access consistently quickly.
Wow that was odd. I just wrote an extremely long comment but after I clicked submit my comment didn’t show
up. Grrrr… well I’m not writing all that over
again. Anyways, just wanted to say great blog!
obviously like your web site but you have to test the spelling
on several of your posts. Many of them are rife with spelling problems
and I to find it very troublesome to tell the truth on the other hand
I will certainly come again again.
Woah! I’m really enjoying the template/theme of this
site. It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between superb usability and appearance.
I must say that you’ve done a very good job with this.
Also, the blog loads extremely fast for me on Chrome.
Outstanding Blog!
Thankfulness to my father who informed me on the topic of this
weblog, this weblog is genuinely remarkable.
Awesome blog article.Really thank you! Awesome.
Major thanks for the blog.Really thank you! Cool.
I really enjoy the blog.Really thank you! Keep writing.
Im grateful for the blog.Thanks Again. Fantastic.
A round of applause for your article post.Really thank you! Much obliged.
Looking forward to reading more. Great post.Much thanks again. Really Great.
I value the blog.Really looking forward to read more. Want more.
Enjoyed every bit of your article post.Thanks Again. Will read on…
Thanks so much for the blog.Much thanks again. Cool.
Appreciate you sharing, great blog article.Thanks Again. Want more.
Very informative post.Much thanks again.
Fantastic blog.Really thank you!
Im obliged for the blog post.Much thanks again. Will read on…
A big thank you for your blog article.Thanks Again. Great.
Muchos Gracias for your article.Much thanks again. Really Cool.
I truly appreciate this blog article.Really looking forward to read more. Really Great.
Hey, thanks for the blog.Thanks Again. Really Cool.
Thanks again for the article post.Really thank you! Really Cool.
It’s an awesome article designed for all the internet users; they will obtain advantage from it I am sure.
A big thank you for your blog post.Much thanks again. Awesome.
Appreciate you sharing, great blog post.Really thank you!
This is one awesome blog post.Really thank you! Want more.
Hey, you used to write fantastic, but the last few posts have been kinda boring… I miss your great writings. Past several posts are just a bit out of track! come on!
Great, thanks for sharing this article.Really thank you! Cool.
I really enjoy the post.Really looking forward to read more. Really Cool.
Very informative post.Thanks Again. Much obliged.
Thanks for sharing, this is a fantastic blog. Cool.
Muchos Gracias for your blog article.Thanks Again. Will read on…
I truly appreciate this blog article.Thanks Again. Want more.
Really enjoyed this article post.Thanks Again. Really Great.
Im obliged for the post. Awesome.
Thank you ever so for you blog article.Thanks Again. Fantastic.
Say, you got a nice post. Fantastic.
I cannot thank you enough for the article.Really thank you! Really Great.
Im grateful for the post.Much thanks again. Really Cool.
wow, awesome post.Thanks Again. Really Great.
Major thankies for the article.Thanks Again. Much obliged.
I am so grateful for your article. Great.
Great, thanks for sharing this post.Much thanks again. Much obliged.
I cannot thank you enough for the article post.Really thank you!
I appreciate you sharing this article.Much thanks again. Want more.
Thanks for the blog article.Much thanks again. Will read on…
Fantastic article post.Thanks Again. Will read on…
Thank you ever so for you post.Much thanks again. Want more.
Major thankies for the article. Awesome.
I really like and appreciate your blog.Really looking forward to read more. Really Great.
Thanks-a-mundo for the article post.Really looking forward to read more. Much obliged.
I cannot thank you enough for the article.Really looking forward to read more. Will read on…
Im thankful for the article.Really looking forward to read more. Cool.
I loved your blog post.Much thanks again. Fantastic.
Really appreciate you sharing this blog article.Much thanks again. Awesome.
Say, you got a nice post. Really Great.
Thank you ever so for you article post.Really thank you! Great.
Thank you ever so for you blog.Really thank you! Much obliged.
Really enjoyed this article. Fantastic.
Really enjoyed this blog.Much thanks again. Awesome.
wow, awesome blog post. Great.
Wow, great blog.Really looking forward to read more. Keep writing.
Very informative blog post.Much thanks again. Keep writing.
Great, thanks for sharing this article post.Thanks Again. Will read on…
I appreciate you sharing this article.Really thank you! Awesome.
Do an individual mind if I estimate a couple of your own posts as long since I provide credit and even sources back to your own blog? My blog will be in the same market as yours, and my personal users would benefit through some of the data you provide here. Remember to let me know when this ok with a person. Thank you.
Muchos Gracias for your blog post.Thanks Again. Want more.
Muchos Gracias for your blog article.Really thank you! Want more.
Thank you for your post.Thanks Again. Fantastic.
Say, you got a nice article post. Great.
Does your website have a contact site? I’m having problems discovering it but, I’d such as to shoot you a good email. I’ve got a few recommendations for your blog site you will be interested in reading.
Thank you ever so for you post.Thanks Again. Awesome.
오피 사이트 Our system of inside jokes is so advanced that only you and I get it. And I like that.