# 【Tsinsen 1280】最长双回文串

#include<iostream>
#include<cstdio>
#include<cstring>
#include
<map>
using namespace std;

const int MAXN = 200000+9;
char pat[MAXN],BUF[MAXN/2];
int n,len[MAXN],vout;

map<int,int>::iterator itr;
map<int,int> Q;

inline void manacher(){
int mx = 0;
for (int i=1;i<=n;i++){ if (mx+len[mx] > i) len[i] = min(len[mx*2-i],mx+len[mx]-i);
else len[i] = 0;
while (pat[i+len[i]+1] == pat[i-len[i]-1]) len[i]++;
if (len[i]+i > len[mx]+mx) mx = i;
}
}

inline void init(){
scanf("%s",BUF+1);
n = strlen(BUF+1); vout = 2;
for (int i=1;i<=n;i++){
pat[i*2-1] = '*';
pat[i*2] = BUF[i];
} pat[n*2+1] = '*';
n=n*2+1; pat[0]='@'; pat[n+1]='&';
}

inline void solve(){
for (int i=1;i<=n;i++){ itr = Q.lower_bound(i-len[i]); if (itr != Q.end()){ int p = itr->second;
vout = max(vout,i-p);
}

if ((Q.insert(make_pair(i+len[i], i))).second){
itr = Q.find(i+len[i]);
if (i >= (++itr)->second && itr != Q.end()) Q.erase(--itr);
else{
itr--;
while (itr != Q.begin() && (--itr)->second >= i) Q.erase(itr), itr=Q.find(i+len[i]);
}
}
}
}

int main(){
init();
manacher();
solve();
printf("%d\n",vout);
return 0;
}


## 82 thoughts to “【Tsinsen 1280】最长双回文串”

1. An outstanding share! I’ve just forwarded this onto
a friend who was conducting a little homework on this. And he in fact bought me lunch due to the fact that I found it
for him… lol. So allow me to reword this….
Thank YOU for the meal!! But yeah, thanx for spending some time to discuss this matter here on your
blog.

2. What a information of un-ambiguity and preserveness of valuable experience regarding
unpredicted emotions.

3. g说道：

Thanks for ones marvelous posting! I really enjoyed reading it, you’re a great
author. I will be sure to bookmark your blog and may come
back at some point. I want to encourage you continue your great job,
have a nice evening!

4. g说道：

Hey there! This is kind of off topic but I need some help from an established blog.
Is it very difficult to set up your own blog? I’m not very techincal but I
can figure things out pretty fast. I’m thinking about making my own but I’m not sure where to
start. Do you have any ideas or suggestions?
Thanks

5. Hi to all, how is the whole thing, I think every one is
getting more from this site, and your views are nice in favor of new users.

6. Hello, I believe your website might be having browser
compatibility issues. Whenever I take a look at your web site in Safari,
it looks fine however, if opening in IE, it’s got some overlapping issues.
I merely wanted to provide you with a quick heads
up! Apart from that, wonderful website!

7. Wow, superb weblog layout! How long have you ever been blogging for?
you make running a blog look easy. The overall
look of your website is great, let alone the content!

8. Greate pieces. Keep writing such kind of info on your site.

Im really impressed by your blog.
Hey there, You’ve done an excellent job. I will certainly digg it and for my part suggest to my friends.
I’m sure they’ll be benefited from this site.

9. each time i used to read smaller content which as well clear their motive, and
that is also happening with this post which I am reading at this
time.

10. That is very fascinating, You are an overly professional blogger.
I’ve joined your feed and stay up for searching for more of your magnificent
post. Also, I’ve shared your website in my social networks

11. For latest news you have to pay a quick visit the web and on web I found this web site
as a best web site for most recent updates.

12. It’s a shame you don’t have a donate button!
I’d most certainly donate to this outstanding blog!
I guess for now i’ll settle for bookmarking and

Talk soon!

13. Magnificent goods from you, man. I’ve understand your stuff previous to and you’re just
extremely magnificent. I actually like what you have acquired here,
certainly like what you are stating and the way in which you say it.

You make it enjoyable and you still care for to keep it wise.
I can not wait to read much more from you.

This is actually a great site.

14. Hi there exceptional website! Does running a blog like this require
a lot of work? I have very little knowledge of coding but I had
been hoping to start my own blog soon. Anyway, if
you have any recommendations or techniques for new blog owners please share.
I know this is off topic but I simply needed to ask. Thanks!

15. Quality content is the main to interest the users to pay a quick visit the site, that’s what this site is providing.

16. Wow, incredible blog layout! How long have you ever been running a blog for?
you make running a blog glance easy. The whole look of your web site is
magnificent, as smartly as the content material!

17. These are genuinely fantastic ideas in on the topic of blogging.
You have touched some fastidious things here. Any way keep up wrinting.

18. Write more, thats all I have to say. Literally, it seems as though you relied on the
video to make your point. You definitely know what youre talking
about, why throw away your intelligence on just posting videos to your
blog when you could be giving us something informative to read?

19. Hello There. I found your blog using msn. This is an extremely well written article.
your useful info. Thanks for the post. I’ll definitely comeback.

natalielise pof

20. I’ve been surfing on-line more than three hours these days,
but I by no means discovered any fascinating article like yours.
It’s pretty price enough for me. Personally, if all website owners and bloggers made good content material as
you did, the internet might be a lot more helpful than ever before.

21. Great beat ! I would like to apprentice at the same time
as you amend your site, how can i subscribe for a blog website?
The account aided me a applicable deal. I were a little bit familiar of

22. Simply wish to say your article is as astonishing. The clarity in your submit is simply nice and i can assume
you are knowledgeable in this subject. Well with your permission allow me to grab

Thank you 1,000,000 and please continue the gratifying work.

23. Great delivery. Great arguments. Keep up the good spirit.

24. Howdy! Do you know if they make any plugins to assist
with SEO? I’m trying to get my blog to rank for some
targeted keywords but I’m not seeing very good success.
If you know of any please share. Appreciate it!

25. I’ve read a few good stuff here. Definitely worth bookmarking for revisiting.
I surprise how much attempt you set to create such a fantastic
informative site. natalielise plenty of fish

26. Hey very nice site!! Guy .. Beautiful .. Wonderful ..
I’m satisfied to seek out numerous helpful information here in the put up, we’d like develop more strategies on this regard,
thanks for sharing. . . . . .

27. Ahaa, its pleasant dialogue regarding this paragraph at this place at this web site, I
have read all that, so at this time me also commenting here.

28. all the time i used to read smaller content that as well
clear their motive, and that is also happening with this paragraph which I am reading now.

29. 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 months of hard work due to no backup.

Do you have any methods to prevent hackers?

30. I have been browsing on-line greater than three
hours nowadays, yet I by no means discovered any fascinating article like
yours. It’s lovely value sufficient for me.
In my opinion, if all webmasters and bloggers made
just right content as you did, the internet shall be a lot

31. Its such as you read my thoughts! You appear to understand a lot
I believe that you just could do with a few % to drive the message house a bit,
I will certainly be back.

32. I’m amazed, I have to admit. Seldom do I come across a blog that’s both educative and entertaining, and without a doubt, you have hit the
nail on the head. The problem is something that too
few men and women are speaking intelligently about. Now i’m very happy that I stumbled across
this in my hunt for something relating to this.

33. Hello! This is my first visit to your blog! We are
a team of volunteers and starting a new initiative in a
community in the same niche. Your blog provided us useful information to
work on. You have done a wonderful job!

34. I enjoy what you guys are up too. This sort of clever work and
coverage! Keep up the good works guys I’ve incorporated you guys to our blogroll.

35. This piece of writing is genuinely a fastidious one it assists new net viewers,
who are wishing in favor of blogging.

36. Currently it looks like WordPress is the preferred
blogging platform available right now. (from what I’ve

37. That is really fascinating, You are an overly professional blogger.

Also, I’ve shared your website in my social networks

38. Howdy! This post couldn’t be written much better! Looking at this

I am going to send this post to him. Pretty sure he’ll have a good read.
I appreciate you for sharing!

39. If you desire to take a great deal from this piece of writing then you have to
apply such strategies to your won blog.

40. You actually make it seem so easy with your presentation but I find this matter to be actually something that I think I
would never understand. It seems too complicated
and extremely broad for me. I’m looking forward for your next post, I will
try to get the hang of it!

41. I pay a visit day-to-day a few web pages and blogs to read content, however
this web site presents feature based content.

42. My brother suggested I may like this blog. He was once entirely right.

This post actually made my day. You can not imagine just how much time I had spent
for this information! Thank you!

43. Woah! I’m really enjoying the template/theme of this website.
It’s simple, yet effective. A lot of times it’s difficult to get that “perfect balance” between user friendliness and visual appearance.
I must say you have done a very good job with this.
Also, the blog loads extremely fast for me on Firefox.
Outstanding Blog!

44. Appreciating the commitment you put into your website and in depth information you provide.
It’s great to come across a blog every once in a while
that isn’t the same out of date rehashed material.

45. I know this website presents quality depending content and
other information, is there any other site which presents these kinds of information in quality?

46. hi!,I love your writing so so much! proportion we communicate extra about
your article on AOL? I need a specialist in this house
to unravel my problem. Maybe that is you! Having a look ahead to
see you.

47. Appreciate the recommendation. Let me try it out.

48. Thanks for sharing your info. I really appreciate your efforts and I will be waiting
for your further post thank you once again.

49. What’s up every one, here every person is sharing these experience, so it’s nice to read this weblog, and I used to go to see this weblog daily.

50. Useful info. Fortunate me I discovered your site accidentally,
and I’m shocked why this accident didn’t came about earlier!
I bookmarked it.

or something. I think that you can do with some pics to drive the
message home a little bit, but other than that, this is magnificent blog.
A fantastic read. I will certainly be back.

52. Wow! This blog looks just like my old one! It’s on a entirely
different topic but it has pretty much the same layout and design. Outstanding choice of colors!

53. Thank you for some other informative website. The place else may
I am getting that type of information written in such a perfect means?
I’ve a project that I’m simply now operating on, and I have been on the glance out for such information.

54. This website was… how do you say it? Relevant!!
Finally I have found something that helped me.

Thanks a lot!

55. excellent issues altogether, you just won a new reader.
a few days in the past? Any sure?

56. magnificent put up, very informative. I wonder why the opposite specialists of this sector don’t notice this.

57. Very shortly this web page will be famous amid all blogging
visitors, due to it’s nice posts

58. When someone writes an paragraph he/she keeps the thought of a user
in his/her mind that how a user can be aware of it. Thus
that’s why this piece of writing is outstdanding.
Thanks!

59. Great post. I will be experiencing a few of these issues as well..

60. Asking questions are genuinely good thing if you are not understanding anything totally,
except this post provides fastidious understanding even.

61. hi!,I really like your writing so so much!
proportion we keep up a correspondence extra approximately your post on AOL?
I require a specialist in this area to resolve my problem.
Maybe that’s you! Taking a look ahead to see you.

Pretty sure he’ll have a good read. Many thanks for sharing!

63. Hi, after reading this remarkable post i am too happy to
share my knowledge here with colleagues.

64. Hello there, You’ve done a great job. I’ll certainly digg it and personally recommend to my friends.

I am sure they’ll be benefited from this site.

65. It’s actually a great and helpful piece of info.
I am glad that you simply shared this useful info with us.

Please stay us informed like this. Thank you for
sharing.

66. Hiya very nice blog!! Guy .. Excellent ..
put up, we’d like work out more techniques in this regard, thank you for sharing.
. . . . .

67. If some one desires expert view on the topic of blogging and
site-building afterward i propose him/her to go to see this
web site, Keep up the pleasant job.

68. This is very fascinating, You’re an excessively professional blogger.
post. Also, I’ve shared your web site in my social networks

but this post is actually a good article, keep it up.

70. Hi there, this weekend is fastidious for me, as this moment i am reading
this great informative article here at my residence.

71. It’s very easy to find out any topic on web
this website.

issue. I love all the points you’ve made.

73. Amazing! This blog looks just like my old one! It’s on a entirely different subject but it has pretty much the same layout and design. Superb choice of colors!

74. This paragraph will assist the internet visitors for setting
up new web site or even a weblog from start to end.

75. Hi! I’ve been reading your web site for a long time now and finally got the courage to go ahead
and give you a shout out from Dallas Tx! Just wanted to mention keep up the fantastic job!

76. Superb blog! Do you have any suggestions for aspiring writers?
I’m planning to start my own website soon but I’m a little lost on everything.

Would you propose starting with a free platform like WordPress or go for
a paid option? There are so many choices out there that I’m totally
confused .. Any ideas? Thank you!

77. Link exchange is nothing else except it is just placing the other person’s
weblog link on your page at suitable place and other person will
also do similar in support of you.

78. Excellent pieces. Keep writing such kind of information on your blog.
Im really impressed by your site.
Hey there, You have performed an incredible job. I will
definitely digg it and personally recommend to my friends.

I am confident they’ll be benefited from this site.

79. It’s amazing in support of me to have a site, which is helpful designed for my know-how.