题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3518
数据生成器：http://paste.ubuntu.com/18021072/
这个，我是SA乱搞，时间复杂度O(n^3)QAQ，不过要把我卡到这个时间复杂度的数据貌似不好出
还是说说正解吧：枚举长度，然后height[]数组分组搞一搞，又是论文题QAQ
其实最开始想的是SAM，每个节点记录一个最先出现的位置和最后出现的位置，而且这样的话，貌似可以做到O(n)
但是懒得写啦！ 还是上一个SA的乱搞代码就水过了吧！
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 3000+9;
char pat[MAXN]; int n;
namespace Suffix_Array{
#define SA Suffix_Array
#define SIGMA_SIZE 26
int sa[MAXN],bot[MAXN],*tmp,*rank;
int t1[MAXN],t2[MAXN],height[MAXN],m;
inline void GetHeight(){
for (int i=1,t,p1,p2;i<=n;i++)if(rank[i]>1){
t = max(0,height[rank[i-1]]-1);
p1 = i+t; p2 = sa[rank[i]-1]+t;
while (pat[p1++]==pat[p2++]) t++;
height[rank[i]] = t;
}
}
inline void build(){
memset(sa,0,sizeof(sa));
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
memset(height,0,sizeof(height));
memset(bot,0,sizeof(bot));
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;
m = rank[sa[1]] = 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); m = rank[sa[1]] = 1;
for (int i=2;i<=n;i++)
if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]]=m;
else rank[sa[i]] = ++m;
if (m >= n) break;
}
GetHeight();
}
inline bool judge(int w, int len){
int mn=sa[w]-len, mx=sa[w]+len;
while (w < n && height[w+1]>=len)
if (sa[++w] <= mn || sa[w] >= mx)
return true;
return false;
}
inline void solve(){
int vout = 0;
for (int i=1;i<=n;i++){
int len=n-sa[i]-height[i]+1;
for (int j=len;j;j--)
if (judge(i,j+height[i]))
{vout += j; break;}
}
printf("%d\n",vout);
}
};
int main(){
while (~scanf("%s",pat+1) && pat[1] != '#'){
SA::build();
SA::solve();
}
return 0;
}
It’s hard to come by educated people about this
subject, however, you seem like you know what you’re talking
about! Thanks
This is my first time go to see at here and i am in fact impressed to
read all at one place.
My programmer is trying to convince 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 several websites for about a year and am worried about switching to another platform.
I have heard good things about blogengine.net.
Is there a way I can import all my wordpress posts into it?
Any help would be greatly appreciated!
I am in fact thankful to the owner of this web page who has shared this fantastic post at here.
Hey! Someone in my Facebook group shared this site with us so I came to give it a look.
I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
Superb blog and superb design.
Hi, I do believe this is a great website. I stumbledupon it 😉 I’m going to revisit
yet again since i have book-marked it. Money and freedom
is the best way to change, may you be rich and continue to
guide other people.
Hi, just wanted to mention, I enjoyed this blog post.
It was helpful. Keep on posting!
Wow, this post is nice, my younger sister is analyzing these kinds
of things, therefore I am going to convey her.
Wonderful post however I was wanting to know if you could
write a litte more on this subject? I’d be very grateful if you could elaborate a little bit further.
Thank you!
Definitely believe that which you said. Your favorite reason seemed to be on the internet the simplest thing to be aware of.
I say to you, I definitely get irked while people consider worries that they plainly do not
know about. You managed to hit the nail upon the top and
also defined out the whole thing without having side effect , people can take a signal.
Will likely be back to get more. Thanks
Very good information. Lucky me I recently found your blog by
accident (stumbleupon). I have bookmarked it for later!
Thanks for some other informative site. The place else may just I get that kind of information written in such
an ideal method? I’ve a mission that I’m just now operating on, and I’ve been at the
glance out for such info.
Incredible story there. What occurred after?
Thanks!
You really make it seem really easy along with your presentation but I in finding this topic
to be really something that I believe I’d by no means understand.
It sort of feels too complicated and extremely wide for me.
I’m having a look ahead to your next publish, I will try to get the hold
of it!
Wow, incredible weblog format! How long have you been blogging for?
you make blogging glance easy. The overall glance of your website is magnificent, as smartly as the content material!
Terrific post but I was wondering if you could write a litte more on this subject?
I’d be very thankful if you could elaborate a little bit more.
Many thanks!
It’s a pity you don’t have a donate button! I’d most certainly donate to this fantastic blog!
I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google account.
I look forward to fresh updates and will share this website with my Facebook
group. Chat soon!
Awesome website you have here but I was curious if you knew of any community forums that
cover the same topics talked about in this article?
I’d really love to be a part of group where I can get feedback from other
experienced people that share the same interest.
If you have any recommendations, please let me know. Many
thanks!
Every weekend i used to pay a quick visit this site,
as i want enjoyment, for the reason that this this web page conations truly fastidious funny material
too.
Everything is very open with a precise explanation of the issues.
It was really informative. Your site is extremely helpful.
Many thanks for sharing!
continuously i used to read smaller content that as well clear their motive, and that is also happening
with this post which I am reading now.
This is a topic that is close to my heart… Take
care! Exactly where are your contact details though?
I don’t even know how I ended up here, but I thought this post was
good. I do not know who you are but definitely you’re going to a famous blogger if you aren’t already 😉 Cheers!
It’s actually a cool and useful piece of info. I’m happy that you simply shared this helpful information with
us. Please stay us up to date like this. Thanks for sharing.
It is not my first time to pay a quick visit this
web page, i am visiting this web site dailly and obtain fastidious facts from here every day.
I seriously love your blog.. Very nice colors & theme. Did you build this amazing site yourself?
Please reply back as I’m wanting to create my own site and
want to know where you got this from or just what the theme is called.
Many thanks!
Wow, amazing blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your website is excellent, let alone the content!
My relatives all the time say that I am killing my time here
at net, however I know I am getting experience daily by reading
such good articles or reviews.
I used to be able to find good info from your content.