【51NOD 1154】回文串划分

相关链接

题目传送门: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;
}

84 thoughts to “【51NOD 1154】回文串划分”

  1. 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];
    ~~~~^

    1. 这个是wordpress的那个辣鸡代码高亮的插件的锅
      他把我所有的`ch[w][c]`渲染成了`ch[w]`,因为`[c]`是它的保留字,代表C语言 QwQ

  2. 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?

  3. 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!

  4. 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

  5. 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!

  6. 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!

  7. 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.

  8. 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.

  9. 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

  10. 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.

  11. 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.

  12. 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

  13. 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.

  14. 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

  15. 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!

  16. 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!

  17. 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?

  18. 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!

  19. 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

  20. 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.

  21. 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!

  22. 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.

  23. 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.

  24. 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.

  25. 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

  26. 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.

  27. 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!

  28. 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!

  29. 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.

  30. 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!

  31. 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.

  32. 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!!

  33. 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.

  34. 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!

  35. 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

  36. 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.

  37. 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!

  38. 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!

  39. 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!

Leave a Reply to ps4 games Cancel reply

Your email address will not be published. Required fields are marked *