【BZOJ 3620】似乎在梦中见过的样子

Qizy KMP, 字符串, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3620
离线版题目：http://paste.ubuntu.com/17950176/

求字串的前缀和后缀相等。WTF，这不14年的动物园吗？
又用到KMP的fail_chain就是从大到小遍历原串前缀的前后缀相等长度
然后O(n^2)暴力
1A! 撒花！ *★,°*:.☆\(￣▽￣)/$:*.°★*

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

const int MAXN = 15000+9;

char pat[MAXN];
int fail[MAXN],vout,N,k;

inline void solve(char *s, int n){
	fail[0] = fail[1] = 0;
	for (int i=2,j=0;i<=n;i++){
		while(j && s[j+1] != s[i]) j = fail[j];
		if (s[j+1] == s[i]) j++;
		fail[i] = j;
	}
	for (int i=k*2+1,t=i;i<=n;i++,t=i) { while ((fail[t])*2+1 > i) t = fail[t];
		if (fail[t] >= k) vout++; 
	}
}

int main(){
	scanf("%s%d",pat+1,&k);
	N = strlen(pat+1);
	for (int i=1;i<=N-k*2;i++)
		solve(pat+i-1,N+1-i);
	printf("%d\n",vout);
	return 0;
}

其实之前想了一想，貌似SA有希望在O（n）的时间复杂度内解决？
搞出sa[]之后，上下以k为限制扫一扫，统计统计。但这样时间复杂度我只能证到是O(n^2)的，还常数还比KMP大

288 thoughts to “【BZOJ 3620】似乎在梦中见过的样子”

  40. It’s a shame you don’t have a donate button! I’d without a doubt donate
    to this superb blog! I suppose for now i’ll settle for book-marking and adding your RSS feed to my Google account.

    I look forward to brand new updates and will talk about this blog with my Facebook group.
    Chat soon!

    Reply

  51. Hey There. I discovered your weblog the usage of msn. This is a really well written article.
    I will be sure to bookmark it and return to learn extra
    of your useful info. Thank you for the post. I will definitely
    return.

    Reply

  73. My partner and I stumbled over here different web page and thought
    I may as well check things out. I like what I see
    so i am just following you. Look forward to looking at your web page
    for a second time.

    Reply

  84. Pretty part of content. I just stumbled upon your site and in accession capital to assert that I acquire
    actually loved account your blog posts. Anyway I will be subscribing in your
    feeds and even I achievement you access persistently quickly.

    Reply

  92. Hi there! I know this is kinda off topic but I’d figured I’d ask.
    Would you be interested in trading links or maybe guest writing a blog post or
    vice-versa? My blog addresses a lot of the same
    topics as yours and I believe we could greatly benefit from
    each other. If you happen to be interested
    feel free to shoot me an e-mail. I look forward to hearing from you!
    Awesome blog by the way!

    Reply

  98. Greetings from Los angeles! I’m bored to death
    at work so I decided to check out your site on my iphone during lunch
    break. I love the information you present here
    and can’t wait to take a look when I get home.
    I’m amazed at how quick your blog loaded on my mobile .. I’m not even using WIFI, just 3G ..
    Anyhow, wonderful blog!

    Reply

  101. I blog frequently and I really appreciate your information. This great article has truly peaked my
    interest. I’m going to take a note of your website and
    keep checking for new information about once per week.
    I opted in for your Feed as well.

    Reply

  105. Hi! 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 problems 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.

    Reply

  139. Hey there! I know this is sort of off-topic however I needed to ask.
    Does building a well-established blog such as yours take
    a lot of work? I’m completely new to blogging however I do write in my journal
    every day. I’d like to start a blog so I will be able to share
    my own experience and feelings online. Please let me know if you have
    any ideas or tips for new aspiring bloggers.
    Thankyou!

    Reply

  144. Hi there I am so excited I found your website,
    I really found you by accident, while I was searching on Bing for something else, Anyhow I am here now and would just like to say cheers for a remarkable post and a all round entertaining
    blog (I also love the theme/design), I don’t have time to look over it all at the moment but I have book-marked it and also
    included your RSS feeds, so when I have time I will be back to read a lot
    more, Please do keep up the superb jo.

    Reply

  158. I’ve been exploring for a bit for any high-quality articles or blog posts in this kind
    of house . Exploring in Yahoo I eventually stumbled upon this web site.
    Studying this info So i’m glad to show that I have an incredibly excellent uncanny feeling I found
    out exactly what I needed. I most for sure will make certain to don?t forget this site and give it
    a look on a continuing basis.

    Reply

  173. Have you ever considered creating an ebook or guest
    authoring on other sites? I have a blog centered on the same subjects you discuss and would love
    to have you share some stories/information. I know my subscribers would appreciate your work.
    If you’re even remotely interested, feel free to shoot me an e mail.

    Reply

  174. After going over a few of the blog articles on your site, I really appreciate your technique of blogging.

    I saved as a favorite it to my bookmark webpage list and will be checking back soon. Please visit my web site too and tell me your opinion.

    Reply

  178. Ahaa, its pleasant discussion about this article at this place at this weblog, I have read all that,
    so at this time me also commenting here.

    Reply

  191. I will immediately clutch your rss as I can not in finding your
    email subscription hyperlink or newsletter service.

    Do you’ve any? Kindly permit me understand so that I may subscribe.

    Thanks.

    Reply

  220. Hello There. I found your blog using msn. This is a very well written article. I will be sure to bookmark it and come back to read more of your useful information. Thanks for the post. I will certainly comeback.

    Reply

  223. How long does a copyright last on newspaper articles?. . If a service copies newspapers articles and then posts it in a database on the Internet, is there also a copyright on the Internet content?.

    Reply

  225. If you are great, you will attempt to bluff your opponents and make them think that you have a extremely good hand. This method is a great deal easier for people to be comfortable with telling you.

    Reply

  234. I just want to say I am very new to blogs and truly savored you’re web site. More than likely I’m likely to bookmark your website . You amazingly come with superb articles and reviews. Regards for sharing your webpage.

    Reply

  241. nike air max 1 sd 850 billiggame brian hartline mens jersey miami dolphins 82 alternate orange nfl billig,nike arizona cardinals 15 michael floyd white limited womens jersey billig,detroit tigers blank 2013 white jersey billig,women nike new orleans saints 66 ben grubbs game blac…

    Reply

  243. I’m extremely impressed with your writing skills as well as with the layout on your blog. Is this a paid theme or did you customize it yourself? Anyway keep up the nice quality writing, it’s rare to see a great blog like this one nowadays..

    Reply

  246. It’s actually a nice and useful piece of information. I’m satisfied that you shared this helpful information with us. Please keep us informed like this. Thank you for sharing.|

    Reply

  250. I really like your blog.. very nice colors & theme. Did you create this website yourself or did you hire someone to do it for you? Plz reply as I’m looking to design my own blog and would like to find out where u got this from. appreciate it|

    Reply

  268. Do you mind if I quote a few of your posts as long as I provide credit and sources back to your site? My blog site is in the exact same area of interest as yours and my visitors would truly benefit from a lot of the information you present here. Please let me know if this ok with you. Many thanks!|

    Reply

  272. My partner and I stumbled over here coming from a different website and thought I might as well check things out. I like what I see so now i’m following you. Look forward to looking into your web page yet again.|

    Reply

  274. What i do not understood is in fact how you are not actually a lot more neatly-favored than you might be right now. You’re so intelligent. You realize thus considerably in relation to this subject, produced me for my part consider it from so many various angles. Its like women and men are not interested unless it is something to accomplish with Lady gaga! Your individual stuffs outstanding. Always care for it up!|

    Reply

  279. May I simply just say what a relief to discover someone who genuinely understands what they’re discussing over the internet. You definitely know how to bring a problem to light and make it important. More people have to look at this and understand this side of your story. It’s surprising you aren’t more popular because you certainly possess the gift.|

    Reply

  288. I just like the valuable information you supply in your articles. I will bookmark your weblog and take a look at once more right here regularly. I am rather certain I will be told plenty of new stuff proper here! Best of luck for the next!|

    Reply

Leave a Reply

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