相关链接
题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1154
数据生成器:http://paste.ubuntu.com/24310870/
解题报告
可以用鏼爷今年WC讲的技巧把时间复杂度优化到$O(n \log n)$
为了好写,我套了一个$PAM$,不过鏼爷讲直接维护就可以了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000000; const int SGZ = 26; const int INF = 1e9; class Palindromic_Tree{ int tot,cnt,last,fail[N],len[N],ch[N][SGZ]; int dif[N],nxt[N],ans[N],f[N]; public: inline int build(char *s) { fail[0] = fail[1] = cnt = last = 1; tot = strlen(s); len[1] = -1; for (int i=0;i<tot;i++) { insert(s, i, s[i]-'a'); update(i); } return ans[tot-1]; } private: inline void insert(char *s, int p, int c) { int w = last; for (;s[p-len[w]-1]!=s[p];w=fail[w]); if (!ch[w]) { int nw=++cnt, t=fail[w]; len[nw] = len[w] + 2; for (;s[p-len[t]-1]!=s[p];t=fail[t]); fail[nw] = ch[t]; ch[w] = nw; dif[nw] = len[nw] - len[fail[nw]]; if (dif[nw] == dif[fail[nw]]) nxt[nw] = nxt[fail[nw]]; else nxt[nw] = fail[nw]; } last = ch[w]; } inline void update(int cur) { ans[cur] = INF; for (int w=last;len[w]>0;w=nxt[w]) { f[w] = ans[cur-len[nxt[w]]-dif[w]] + 1; if (dif[w] == dif[fail[w]]) f[w] = min(f[w], f[fail[w]]); ans[cur] = min(ans[cur], f[w]); } } }PAM; int main() { char pat[N]; cin>>pat; cout<<PAM.build(pat); return 0; }
Compile Error :
t.cpp: In member function ‘void Palindromic_Tree::insert(char*, int, int)’:
t.cpp:29:32: error: invalid conversion from ‘int*’ to ‘int’ [-fpermissive]
fail[nw] = ch[t]; ch[w] = nw;
~~~~^
t.cpp:29:43: error: incompatible types in assignment of ‘int’ to ‘int [26]’
fail[nw] = ch[t]; ch[w] = nw;
^~
t.cpp:35:24: error: invalid conversion from ‘int*’ to ‘int’ [-fpermissive]
last = ch[w];
~~~~^
这个是wordpress的那个辣鸡代码高亮的插件的锅
他把我所有的`ch[w][c]`渲染成了`ch[w]`,因为`[c]`是它的保留字,代表C语言 QwQ
好文章!666,学习了
Hey! I just wanted to ask if you ever have any issues with hackers?
My last blog (wordpress) was hacked and I ended up losing several weeks of hard work due to no backup.
Do you have any solutions to stop hackers?
I have read so many posts concerning the blogger lovers but this paragraph is truly a
pleasant paragraph, keep it up.
I truly love your blog.. Very nice colors & theme.
Did you develop this web site yourself? Please reply back as I’m trying to create my own personal website and would like to know where you got this from or exactly what the theme is called.
Thanks!
Hi everybody, here every one is sharing these know-how, so it’s pleasant to read this webpage, and I used to visit this
website everyday.
continuously i used to read smaller articles or reviews
which as well clear their motive, and that is also happening with this post which I am reading at this time.
Hi! This is kind of off topic but I need some advice from an established blog.
Is it difficult to set up your own blog?
I’m not very techincal but I can figure things out pretty fast.
I’m thinking about creating my own but I’m not sure where to start.
Do you have any points or suggestions? Thanks
Having read this I believed it was really enlightening.
I appreciate you spending some time and energy to put this content together.
I once again find myself spending a lot of time both reading and commenting.
But so what, it was still worthwhile!
Someone essentially lend a hand to make severely articles
I might state. This is the very first time
I frequented your web page and up to now? I surprised with the analysis you made to create this particular post amazing.
Great activity!
hello there and thank you for your information – I have definitely picked up anything new from right here.
I did however expertise several technical points using this web site,
as I experienced to reload the web site many times previous to I could get it to load properly.
I had been wondering if your web host is OK? Not that I’m complaining,
but slow loading instances times will often affect your
placement in google and could damage your high-quality score if advertising and marketing with Adwords.
Well I’m adding this RSS to my email and can look out for much more of your respective fascinating content.
Make sure you update this again very soon.
bookmarked!!, I really like your web site!
This site truly has all the information I wanted about this subject and
didn’t know who to ask.
Pretty section of content. I just stumbled upon your site and in accession capital to assert that I acquire
actually enjoyed account your blog posts. Anyway I’ll be subscribing
to your feeds and even I achievement you access consistently quickly.
Good article. I am dealing with some of these issues as well..
Wow that was strange. I just wrote an really long comment but after I
clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over
again. Anyways, just wanted to say fantastic blog!
Hello just wanted to give you a quick heads up. The words in your post seem to be running off the screen in Chrome.
I’m not sure if this is a format issue or something to
do with internet browser compatibility but I figured I’d post to let
you know. The design and style look great though!
Hope you get the problem resolved soon. Cheers
Great information. Lucky me I found your blog
by chance (stumbleupon). I’ve bookmarked it for later!
Your style is really unique compared to other folks I’ve read stuff from.
I appreciate you for posting when you have the opportunity, Guess I will just bookmark this site.
I loved as much as you’ll receive carried out right here.
The sketch is attractive, your authored subject matter stylish.
nonetheless, you command get bought an impatience over that you wish
be delivering the following. unwell unquestionably come further formerly again as
exactly the same nearly very often inside case you shield this increase.
What’s up, its fastidious piece of writing regarding media print, we all be
aware of media is a impressive source of data.
Hey there! Do you use Twitter? I’d like to follow you if that would be ok.
I’m definitely enjoying your blog and look forward to new posts.
Great post. I was checking continuously this blog and
I am impressed! Very helpful information specifically the last part 🙂 I care for such
info much. I was looking for this particular information for a very
long time. Thank you and best of luck.
Hurrah! In the end I got a weblog from where I be able to genuinely take useful facts regarding my study and knowledge.
obviously like your web site however you need to test the spelling on quite a few of your posts.
Many of them are rife with spelling issues and
I in finding it very bothersome to inform the
truth then again I’ll surely come again again. plenty of fish natalielise
Great article. I’m going through many of these issues as well..
plenty of fish natalielise
My spouse and I stumbled over here coming from a different website and thought I may as well check things out.
I like what I see so now i’m following you. Look forward to exploring your
web page repeatedly.
Its like you read my thoughts! You appear to grasp a lot approximately this, like you wrote the e book in it or something.
I think that you just can do with some percent to drive the message house a little bit, however instead of that,
this is wonderful blog. A fantastic read. I’ll certainly be back.
Howdy just wanted to give you a quick heads up.
The text in your article seem to be running off the screen in Firefox.
I’m not sure if this is a format issue or something to do with web browser compatibility but I thought I’d post to let you know.
The style and design look great though! Hope you get the problem fixed
soon. Kudos
Somebody necessarily help to make critically articles I’d state.
This is the first time I frequented your web page and to this
point? I surprised with the research you made
to create this actual post extraordinary. Great process!
You’re so interesting! I don’t believe I’ve truly read something like that before.
So nice to discover another person with a few unique thoughts on this issue.
Really.. thank you for starting this up. This
site is something that is needed on the web,
someone with some originality!
If you want to obtain a great deal from this article then you have to apply these methods to your won weblog.
At this time it appears like BlogEngine is the top blogging platform out there right now.
(from what I’ve read) Is that what you are using on your blog?
I’m really enjoying the theme/design of your website.
Do you ever run into any internet browser compatibility problems?
A few of my blog audience have complained about my
site not operating correctly in Explorer but looks great in Safari.
Do you have any suggestions to help fix this issue?
This website was… how do I say it? Relevant!! Finally I’ve found something that helped me.
Thanks a lot!
Hello! This is my first visit to your blog! We are
a group of volunteers and starting a new project in a community in the same niche.
Your blog provided us valuable information to work on. You have done a wonderful job!
If you wish for to increase your know-how just keep visiting this website and be updated with the most
up-to-date news posted here.
WOW just what I was looking for. Came here by searching for quest
bars cheap
I think this is one of the most significant information for me.
And i am glad reading your article. But want to remark on some general things, The website style is ideal,
the articles is really excellent : D. Good job, cheers
If you desire to increase your know-how just keep visiting this web page and be updated with the
hottest information posted here.
We are a group of volunteers and starting a new scheme in our community.
Your web site offered us with valuable info to work on.
You have done a formidable job and our whole community will be grateful to you.
Hi there! I simply wish to give you a big thumbs up for the excellent info you’ve got right here on this post.
I’ll be returning to your blog for more soon.
Very rapidly this website will be famous amid all blog people,
due to it’s pleasant content
Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your blog?
My website is in the exact same niche as yours and my visitors would definitely benefit from a
lot of the information you present here. Please let me know if this okay with you.
Appreciate it!
Thank you for the auspicious writeup. It actually was a entertainment account it.
Glance advanced to far introduced agreeable from you!
However, how can we be in contact?
I think the admin of this site is actually working hard in favor of his web page, as here every information is quality based data.
We’re a group of volunteers and opening a new scheme in our community.
Your web site provided us with valuable info to work on. You have
done an impressive job and our entire community
will be thankful to you.
Hi, just wanted to tell you, I liked this post.
It was funny. Keep on posting!
Have you ever thought about publishing an ebook or guest authoring on other websites?
I have a blog centered on the same ideas you discuss and would really like to have you share some stories/information. I know my visitors would value your work.
If you’re even remotely interested, feel free to
send me an email.
I’ve been surfing on-line more than 3 hours nowadays, but I never
found any interesting article like yours.
It’s lovely price enough for me. In my view, if all web
owners and bloggers made good content material as you did, the internet will probably be a lot more helpful than ever
before.
Undeniably consider that that you said. Your favourite justification seemed to be
on the net the easiest thing to take into account of.
I say to you, I definitely get annoyed at the same time as folks
consider issues that they plainly don’t realize about.
You controlled to hit the nail upon the top and outlined out
the whole thing without having side-effects , other folks
can take a signal. Will probably be back to get more.
Thank you
I do trust all the ideas you have presented to your
post. They’re very convincing and will certainly work. Still, the posts are very short for newbies.
May you please lengthen them a little from subsequent time?
Thank you for the post.
Genuinely when someone doesn’t understand afterward its up to other users that they will assist, so here it happens.
Wow that was unusual. I just wrote an extremely
long comment but after I clicked submit my comment didn’t appear.
Grrrr… well I’m not writing all that over
again. Anyhow, just wanted to say wonderful blog!
Major thanks for the blog article.Thanks Again. Want more.
I want to to thank you for this good read!! I certainly enjoyed every bit of it.
I’ve got you book-marked to look at new stuff you post…
I read this piece of writing completely on the topic of the difference of latest and previous technologies, it’s
amazing article.
Thanks for sharing your thoughts about plenty of
fish dating site. Regards
Hello to all, how is everything, I think every one is getting more
from this website, and your views are nice in support of new
people.
What’s up, its good post concerning media print, we all be
familiar with media is a wonderful source of facts.
What’s up, I wish for to subscribe for this web
site to get hottest updates, therefore where can i do it please
assist.
The other day, while I was at work, my cousin stole my iPad and tested to
see if it can survive a 30 foot drop, just so she can be a youtube sensation.
My apple ipad is now destroyed and she has 83 views.
I know this is completely off topic but I had to share it with
someone!
Great blog here! Also your website loads up very fast!
What host are you using? Can I get your affiliate link to your host?
I wish my website loaded up as fast as yours lol
Great blog! Do you have any tips and hints for aspiring
writers? I’m planning to start my own blog soon but I’m a little lost on everything.
Would you recommend starting with a free platform like WordPress or go for
a paid option? There are so many options out there that I’m totally
overwhelmed .. Any recommendations? Cheers!
Do you have a spam problem on this site; I also am a blogger, and I was wanting to know your situation; we have created some nice practices and we are looking to trade strategies with others, why not shoot me an email
if interested.
Way cool! Some very valid points! I appreciate you writing this post and also the
rest of the site is also really good.
It’s appropriate time to make a few plans for the longer term and it’s time to
be happy. I have read this put up and if I may just I want to suggest you few interesting things or suggestions.
Perhaps you can write next articles relating to this
article. I wish to learn more issues about it!
Quality articles is the crucial to interest the users to pay a quick visit the site, that’s what this web page is providing.
May I just say what a comfort to discover somebody that really knows what they’re talking about over the internet.
You definitely know how to bring a problem to light and make it important.
A lot more people should read this and understand this side of your story.
I can’t believe you’re not more popular since you definitely possess the gift.
Oh my goodness! Incredible article dude! Thanks, However I am
experiencing issues with your RSS. I don’t understand why I
am unable to join it. Is there anyone else having similar RSS
problems? Anyone who knows the answer will you kindly respond?
Thanx!!
Hello, I check your new stuff on a regular basis. Your humoristic style is awesome, keep up the good
work!
What’s Going down i am new to this, I stumbled upon this I have discovered It positively useful
and it has helped me out loads. I hope to contribute & help different users like
its aided me. Good job.
What’s up to all, for the reason that I am genuinely keen of reading this weblog’s post
to be updated on a regular basis. It contains good stuff.
I like the helpful information you provide in your articles. I will bookmark your blog and check again here regularly. I’m quite sure I will learn plenty of new stuff right here! Best of luck for the next!
Hello colleagues, nice paragraph and pleasant urging commented at this place, I am actually enjoying by these.
I know this if off topic but I’m looking into starting my own weblog and was wondering 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 recommendations or advice would be greatly appreciated.
Cheers
What’s up, all the time i used to check weblog posts here in the early hours in the daylight, as
i enjoy to learn more and more.
Hmm it looks like your website ate my first
comment (it was extremely long) so I guess I’ll
just sum it up what I wrote and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog blogger but I’m still new to the whole thing.
Do you have any points for beginner blog writers?
I’d really appreciate it.
First of all I want to say great blog! I had a quick question that I’d like to
ask if you do not mind. I was interested to know how you center yourself and clear your mind prior to writing.
I’ve had trouble clearing my thoughts in getting my ideas out.
I truly do take pleasure in writing but it just seems like the first 10 to
15 minutes are usually wasted simply just trying to figure out how to begin. Any suggestions or hints?
Thank you!
Wow, this piece of writing is fastidious, my younger sister is
analyzing these kinds of things, so I am going to convey
her.
Very nice post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your
blog posts. After all I’ll be subscribing to your
feed and I hope you write again very soon!
You really make it seem so easy with your presentation but
I find this matter to be actually something which I think I would never understand.
It seems too complicated and very broad for me. I’m looking
forward for your next post, I’ll try to get the hang of it!
This really answered my downside, thank you!