相关链接
题目传送门：http://poj.org/problem?id=3693
数据生成器：http://paste.ubuntu.com/18156993/
题目大意
给定长度为$n(n \le 10^5)$，问循环次数最多的子串循环多少次
请输出字典序最小的解
解题报告
这是SA的 论文题 + 神题
而且SAM貌似不可捉的样子 （╯－＿－）╯╧╧
求符合要求的串已经是身心具疲，这题还要字典序最小，TM恶心到不行 ( ▼-▼ )
还是说一说怎么求符合要求的串吧：
枚举符合要求的串的长度L，那么符合要求的串一定在s[1],s[1+L],s[1+2*L]…..等位置出现(跟今年APIO的交互题有点像)
于是我们就直接height[] + ST表搞定整节循环的部分，这个地方和KMP差不多
只与前面有多少相同的，看起来不好求，但实际上如果对于答案有贡献，那么一定是补足循环节
然后是如何让字典序最小：
一般的题目没这题这么恶心，这题尤其恶心！ MD再掀一次桌子都无法压抑内心的悲伤 （╯－＿－）╯╧╧
这个好像只能用SA数组从小到大枚举，然后判断
哎呀，考场上要是遇到这个题，一定做不对QAQ
Code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 200000+9;
const int SIGMA_SIZE = 26;
char pat[MAXN];
namespace Suffix_Array{
#define SA Suffix_Array
int sa[MAXN],height[MAXN],t1[MAXN],t2[MAXN];
int bot[MAXN],*tmp,*rank,m,n;
int Tm,len[MAXN],TT,cnt;
namespace Sparse_Table{
#define ST Sparse_Table
int MN[MAXN][20];
inline void build(){
for (int i=1;i<=n;i++) memset(MN[i],0,sizeof(MN[i]));
for (int i=1;i<=n;i++) MN[i][0] = height[i];
for (int i=1;i<18;i++){
for (int j=1;j<=n;j++)
MN[j][i] = min(MN[j][i-1],MN[j+(1<<(i-1))][i-1]);
}
}
inline int query(int l, int r){
if (r < l) swap(l, r); l++;
if (l < 1) return -1;
else {
int mid=(l+r)/2,k=0;
while (l+(1<<k)<=mid) k++;
return min(MN[l][k],MN[r-(1<<k)+1][k]);
}
}
};
inline void GetHeight(){
for (int i=1;i<=n;i++) if (rank[i] > 1){
int sta = max(0, height[rank[i-1]]-1);
int p1 = i+sta, p2 = sa[rank[i]-1]+sta;
while (pat[p1++]==pat[p2++]) sta++;
height[rank[i]] = sta;
}
}
inline void build(){
memset(bot,0,sizeof(bot));
memset(height,0,sizeof(height));
tmp = t1; rank = t2;
n = strlen(pat+1); m = SIGMA_SIZE;
for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+1]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++) rank[sa[i]]=(tmp[sa[i]]==tmp[sa[i-1]])?m:++m;
for (int k=1;k<=n;k*=2){ int T=0;
for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
for (int i=1;i<=n;i++) if (sa[i]>k) tmp[++T] = sa[i]-k;
for (int i=1;i<=m;i++) bot[i] = 0;
for (int i=1;i<=n;i++) bot[rank[i]]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
swap(rank, tmp);
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++) if (tmp[sa[i-1]]==tmp[sa[i]] && tmp[sa[i-1]+k]==tmp[sa[i]+k]) rank[sa[i]] = m; else rank[sa[i]] = ++m; if (m >= n) break;
}
GetHeight();
ST::build();
}
inline void solve(){
Tm = 1;
for (int k=1;k<=n;k++){
for (int i=1;i<=n;i+=k){
int sta = ST::query(rank[i],rank[i+k]),T = sta / k + 1;
if (sta % k && ST::query(rank[i-k+sta%k],rank[i+sta%k]) >= k-sta%k) T++;
if (T > Tm){Tm = T; len[cnt=1] = k;}
if (T == Tm) {len[++cnt] = k;}
}
}
if (Tm==1) printf("Case %d: %c\n",++TT,pat[sa[1]]);
else {
for (int i=1;i<=n;i++) for (int j=1;j<=cnt;j++) {
if (ST::query(i,rank[sa[i]+len[j]]) >= (Tm-1)*len[j]) {
pat[sa[i]+Tm*len[j]] = 0;
printf("Case %d: %s\n",++TT,pat+sa[i]);
return;
}
}
}
}
};
int main(){
while (scanf("%s",pat+1) && pat[1] != '#'){
SA::build();
SA::solve();
}
return 0;
}
I do trust all the concepts you’ve offered for your post.
They’re really convincing and can definitely work. Still, the posts
are too short for starters. Could you please prolong them a bit from next
time? Thanks for the post.
It’s an amazing article in support of all the online people; they will obtain benefit from
it I am sure.
Right now it sounds like WordPress is the best blogging platform available right now.
(from what I’ve read) Is that what you are using on your blog?
This design is spectacular! You definitely know how to keep a reader amused.
Between your wit and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Excellent job. I really enjoyed what you had to say, and more than that, how you
presented it. Too cool!
Good write-up. I certainly love this site. Keep writing!
Hi there are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get started and create my own. Do you need any html coding knowledge to make your own blog?
Any help would be greatly appreciated!
Everyone loves what you guys are up too. This type of clever work and coverage!
Keep up the superb works guys I’ve added you guys
to my blogroll.
Heya just wanted to give you a brief heads up and let you know a few of the pictures aren’t loading properly.
I’m not sure why but I think its a linking issue. I’ve tried it in two different web browsers and
both show the same results.
That is a really good tip particularly to those new to the blogosphere.
Short but very precise info… Many thanks for sharing this one.
A must read article!
Good day! This is my 1st comment here so I just wanted to give a quick shout
out and tell you I genuinely enjoy reading your blog posts.
Can you recommend any other blogs/websites/forums that deal with the same topics?
Thank you so much!
Wow, that’s what I was searching for, what a data!
present here at this weblog, thanks admin of this web site.
Undeniably imagine that which you said. Your favourite justification seemed to be on the web the easiest thing to take into
account of. I say to you, I certainly get annoyed even as other people consider
issues that they just do not understand about. You managed to hit the
nail upon the top and defined out the entire thing with no need
side effect , folks could take a signal. Will likely be back to
get more. Thanks
Hi there, its nice paragraph concerning media print, we
all understand media is a wonderful source of data.
You actually make it seem so easy with your presentation but
I find this matter to be really something that I think I would never understand.
It seems too complex and extremely broad for me. I’m looking forward for your next post,
I’ll try to get the hang of it!
Wow, fantastic weblog structure! How lengthy have you been running a blog for?
you made running a blog glance easy. The whole glance
of your web site is fantastic, let alone the content!
If you wish for to obtain a great deal from this paragraph then you
have to apply such techniques to your won website.
Thank you for the auspicious writeup. It if truth be
told was a enjoyment account it. Look advanced to far brought agreeable from you!
By the way, how could we be in contact?
Yes! Finally someone writes about natalielise. natalielise plenty of fish
Write more, thats all I have to say. Literally, it seems as though
you relied on the video to make your point. You clearly know what youre talking
about, why throw away your intelligence on just posting videos to your site when you
could be giving us something informative to read?
I like the helpful info you provide for your articles. I’ll bookmark your weblog and take
a look at again here frequently. I’m somewhat sure I will learn lots of new stuff right
right here! Good luck for the following!
This design is wicked! You definitely know how to keep a reader amused.
Between your wit and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Excellent job. I really loved what you had to say,
and more than that, how you presented it. Too cool!
plenty of fish natalielise
This is a topic that is near to my heart… Best wishes!
Exactly where are your contact details though?
Hurrah, that’s what I was looking for, what a material!
present here at this blog, thanks admin of this web site.
Hmm it looks like your site 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 writer but I’m still new
to the whole thing. Do you have any points for newbie blog writers?
I’d really appreciate it.
Thank you a lot for sharing this with all people you really understand
what you’re speaking about! Bookmarked. Please also seek advice from
my site =). We can have a hyperlink exchange contract between us natalielise plenty of fish
Ahaa, its fastidious dialogue regarding this piece of writing at this place at this web site,
I have read all that, so at this time me also commenting at this place.
Valuable info. Fortunate me I found your website unintentionally,
and I am surprised why this coincidence didn’t took place in advance!
I bookmarked it.
Hi, I think your blog might be having browser compatibility issues.
When I look at your website in Opera, it looks fine but when opening
in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up!
Other then that, terrific blog!
Hi there to every one, for the reason that I am genuinely eager of reading this web site’s post to be updated on a regular basis.
It contains fastidious stuff.
Hi there, constantly i used to check weblog posts here in the early hours in the daylight, since i
like to find out more and more.
Way cool! Some extremely valid points! I appreciate you writing this
write-up and the rest of the website is very good.
Superb blog you have here but I was wanting to know if you knew of any
forums that cover the same topics talked about in this article?
I’d really like to be a part of community where I can get responses from other experienced individuals that share the same interest.
If you have any recommendations, please let me know.
Thanks!
If some one needs expert view about running a blog after that i advise him/her to pay a
visit this webpage, Keep up the good job.
Good day very nice site!! Guy .. Beautiful .. Wonderful
.. I’ll bookmark your web site and take the feeds also?
I’m happy to find numerous helpful information right
here within the publish, we’d like develop more techniques on this regard, thanks for sharing.
. . . . .
This post will help the internet people
for creating new webpage or even a weblog from start to end.
May I simply say what a relief to find somebody that
genuinely understands what they’re discussing on the internet.
You actually realize how to bring a problem to light and make it important.
A lot more people should read this and understand this side of the story.
I was surprised that you’re not more popular given that you
surely possess the gift.
You can certainly see your skills in the work you write. The world hopes for
even more passionate writers such as you who aren’t afraid to say how they believe.
At all times follow your heart.
It’s remarkable for me to have a website, which is useful in support of my experience.
thanks admin
Hi there! Someone in my Myspace group shared this website with us so I came to check it out.
I’m definitely enjoying the information. I’m bookmarking and will be tweeting this to my
followers! Great blog and superb style and design.
Paragraph writing is also a fun, if you know afterward you can write if not it is
difficult to write.
Thanks for finally talking about >【POJ 3693】Maximum repetition substring – Qizy’s Database <Liked it!
I visited many websites however the audio quality for audio songs existing at
this web site is in fact wonderful.
I’m truly enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more pleasant
for me to come here and visit more often. Did you hire out a designer
to create your theme? Outstanding work!
As the admin of this web site is working, no hesitation very rapidly
it will be famous, due to its quality contents.
I’m really impressed with your writing skills as well as with the
layout on your weblog. Is this a paid theme or did you customize it yourself?
Anyway keep up the excellent quality writing,
it’s rare to see a great blog like this one today.
It’s in fact very complicated in this full of
activity life to listen news on TV, so I only use web
for that reason, and obtain the most up-to-date news.
Excellent post. Keep writing such kind of info on your blog.
Im really impressed by it.
Hi there, You have performed an incredible job.
I’ll certainly digg it and in my opinion suggest to my friends.
I’m confident they’ll be benefited from this web site.
My programmer is trying to persuade me to move to .net
from PHP. I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using Movable-type on a number of websites for about a year and am concerned
about switching to another platform. I have heard very good things about blogengine.net.
Is there a way I can transfer all my wordpress content
into it? Any kind of help would be really appreciated!
Hi would you mind sharing which blog platform you’re working
with? I’m going to start my own blog in the near future but I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different
then most blogs and I’m looking for something completely unique.
P.S Apologies for being off-topic but I
had to ask!
Hello there! I just would like to offer you a big
thumbs up for the excellent info you have here on this post.
I’ll be coming back to your site for more soon.
This post is really a nice one it helps new the web people, who
are wishing for blogging.
Hi, I do believe this is a great blog. I stumbledupon it 😉 I am going to come back yet again since I book marked it.
Money and freedom is the greatest way to change, may you be rich and continue to guide other people.
If some one wishes expert view concerning blogging then i recommend
him/her to pay a visit this web site, Keep up the fastidious job.
excellent put up, very informative. I wonder
why the opposite specialists of this sector don’t understand this.
You should proceed your writing. I’m confident, you’ve a great readers’
base already!
Hi there 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 formatting issue
or something to do with internet browser compatibility but I thought
I’d post to let you know. The layout look great though! Hope you get the problem solved soon.
Many thanks
Hmm it looks like your site ate my first comment (it was
extremely long) so I guess I’ll just sum it up what
I submitted and say, I’m thoroughly enjoying your
blog. I as well am an aspiring blog writer but I’m still new to everything.
Do you have any recommendations for inexperienced blog writers?
I’d definitely appreciate it.
Your mode of explaining all in this article is truly good,
every one can effortlessly be aware of it, Thanks a lot.
Whoa! This blog looks exactly like my old one! It’s on a
completely different topic but it has pretty much the same page layout and design. Superb choice of colors!
Howdy I am so thrilled I found your blog, I really found you by error, while I was researching on Askjeeve for
something else, Nonetheless 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 go through it all at the minute but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read a lot more, Please do
keep up the great jo.
Very nice article. I definitely love this site.
Thanks!
Hi i am kavin, its my first occasion to commenting anywhere, when i read this paragraph i
thought i could also create comment due to this sensible paragraph.
I’m not that much of a internet reader to be honest but your sites really nice, keep it up!
I’ll go ahead and bookmark your website to come
back in the future. Many thanks
Undeniably believe that that you said. Your favourite reason seemed to be
on the web the easiest factor to be mindful of. I say to you, I definitely get
irked even as other folks consider worries that they
plainly do not know about. You controlled to hit the
nail upon the top and defined out the entire thing with no need side-effects ,
other people could take a signal. Will likely be back to get more.
Thanks
Attractive section of content. I just stumbled upon your site and in accession capital to assert that I
acquire in fact enjoyed account your blog posts. Anyway I’ll be subscribing
to your feeds and even I achievement you access consistently fast.
It’s really very complex in this busy life to listen news on TV, thus I simply
use web for that purpose, and get the most recent news.
Spot on with this write-up, I honestly think this site
needs a great deal more attention. I’ll probably be returning to read through more, thanks for the information!
I’ve been surfing online more than three hours today,
yet I never found any interesting article like yours. It is pretty worth enough for me.
In my opinion, if all site owners and bloggers made good content as you
did, the net will be a lot more useful than ever before.
Nice post. I learn something totally new and challenging on blogs I stumbleupon everyday.
It will always be interesting to read content from other writers and use something from other
web sites.
Hello, Neat post. There is a problem along with your website in internet explorer,
might check this? IE still is the marketplace leader
and a large portion of other folks will leave out your wonderful writing because of this problem.
Good information. Lucky me I recently found your website by chance (stumbleupon).
I’ve saved it for later!
Valuable info. Fortunate me I found your site
by chance, and I’m shocked why this accident did not happened in advance!
I bookmarked it.
Asking questions are actually fastidious thing if you are not understanding anything
fully, however this paragraph provides fastidious understanding
yet.
You really make it seem so easy with your presentation but I find this topic to be really something
that I think I would never understand. It seems too
complex and extremely broad for me. I’m looking forward for your next post, I’ll try to get the
hang of it!
This article presents clear idea for the new people of blogging, that genuinely how
to do blogging and site-building.
Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across. It extremely helps make reading your blog significantly easier.
We’re a group of volunteers and opening a new scheme in our community.
Your website offered us with valuable info to work on. You’ve done an impressive
job and our entire community will be thankful to you.
Hi there, just wanted to tell you, I liked this blog
post. It was funny. Keep on posting!
Hi there, I desire to subscribe for this blog to take hottest updates, so
where can i do it please help.
If you desire to improve your experience only
keep visiting this website and be updated with the
hottest news posted here.
Hello, i feel that i noticed you visited my web site thus i
got here to go back the prefer?.I’m trying to in finding things to improve
my web site!I assume its ok to use some of your ideas!!
Right away I am going to do my breakfast, later than having my breakfast coming over again to read
additional news.
Excellent beat ! I would like to apprentice while you amend your site,
how could i subscribe for a blog web site? The account helped me a acceptable deal.
I had been tiny bit acquainted of this your broadcast offered bright clear concept
Hi, I do think this is an excellent site. I stumbledupon it 😉 I will revisit once again since i have book marked it.
Money and freedom is the greatest way to change,
may you be rich and continue to help other people.
I’m extremely inspired with your writing abilities as neatly as with the structure to your weblog.
Is this a paid topic or did you customize it yourself?
Either way stay up the nice quality writing, it is rare to look a nice blog
like this one these days..
I all the time emailed this web site post page to all my associates, because if like to
read it after that my contacts will too.
Good post. I learn something new and challenging on websites I stumbleupon on a daily basis.
It will always be helpful to read articles from other writers
and practice a little something from their web sites.
I have read so many content regarding the blogger lovers but this piece of writing
is really a fastidious paragraph, keep it up.
Hello, just wanted to mention, I enjoyed this post. It was
helpful. Keep on posting!
I love it when folks get together and share views. Great blog, continue the good work!
I’m extremely impressed together with your writing abilities and also with the structure to your weblog.
Is this a paid theme or did you customize it your self?
Anyway stay up the nice high quality writing, it’s
uncommon to peer a nice blog like this one nowadays..
hi!,I love your writing very a lot! percentage we be in contact more approximately your post on AOL? I require an expert on this house to solve my problem. May be that is you! Having a look ahead to look you.
Fantastic web site. Plenty of helpful information here.
I’m sending it to some friends ans additionally sharing in delicious.
And certainly, thanks for your effort!
all the time i used to read smaller content that also clear
their motive, and that is also happening
with this article which I am reading at this place.
I loved your blog post.Thanks Again. Awesome.
Hey there! Someone in my Facebook group shared this website
with us so I came to check it out. I’m definitely enjoying the information. I’m book-marking
and will be tweeting this to my followers! Fantastic blog and outstanding design and style.