【Tsinsen 1280】最长双回文串

题目传送门:http://www.tsinsen.com/ViewGProblem.page?gpid=A1280
离线版题目:http://paste.ubuntu.com/17832836/

参考BZOJ_3676

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

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

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

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

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

  7. 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
    adding your RSS feed to my Google account. I look forward to new updates
    and will talk about this site with my Facebook group.

    Talk soon!

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

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

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

  11. Hello There. I found your blog using msn. This is an extremely well written article.
    I’ll be sure to bookmark it and return to read more of
    your useful info. Thanks for the post. I’ll definitely comeback.

    natalielise pof

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

  13. 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
    this your broadcast provided bright clear concept

  14. 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
    your RSS feed to stay up to date with forthcoming post.

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

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

  16. Hey very nice site!! Guy .. Beautiful .. Wonderful ..
    I will bookmark your website and take the feeds additionally?
    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. . . . . .

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

  18. 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
    more helpful than ever before.

  19. Its such as you read my thoughts! You appear to understand a lot
    about this, such as you wrote the ebook in it or something.
    I believe that you just could do with a few % to drive the message house a bit,
    however instead of that, this is magnificent blog. A fantastic read.
    I will certainly be back.

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

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

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

    I’ve joined your feed and look ahead to seeking more of your magnificent post.

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

  23. Howdy! This post couldn’t be written much better! Looking at this
    post reminds me of my previous roommate! He continually kept preaching about this.

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

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

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

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

  27. 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.
    Great read! I’ve bookmarked your site and I’m
    including your RSS feeds to my Google account.

  28. Its like you read my mind! You appear to know so much about this, like you wrote the book in 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.

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

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

  31. magnificent put up, very informative. I wonder why the opposite specialists of this sector don’t notice this.
    You should proceed your writing. I’m sure, you have a great readers’ base already!

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

  33. Hello there! This article could not be written much better!
    Looking through this article reminds me of my previous
    roommate! He constantly kept preaching about this.
    I most certainly will forward this article to him.
    Pretty sure he’ll have a good read. Many thanks for sharing!

  34. Hiya very nice blog!! Guy .. Excellent ..
    Amazing .. I’ll bookmark your blog and take the feeds additionally?
    I am glad to find numerous helpful information here within the
    put up, we’d like work out more techniques in this regard, thank you for sharing.
    . . . . .

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

  36. This is very fascinating, You’re an excessively professional blogger.
    I’ve joined your feed and look ahead to searching for more of your magnificent
    post. Also, I’ve shared your web site in my social networks

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

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

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注