【BZOJ 4319】[CERC2008] Suffix Reconstruction




但当时想了一会儿,感觉不可做,以为是他们记错题目了 QwQ
今天居然看到原题了,但想了很久,还是只会$O(26 \cdot n \log{n})$

先来说说$O(26 \cdot n \log{n})$的做法吧!


所以这么做是对的,时间复杂度:$O(26 \cdot n^2)$
于是我们可以二分每一个字符地分界点,这样复杂度就是$O(26 \cdot n \log{n})$的了

如果$rank[sa[i]+1] > rank[sa[i+1]+1]$的话,那么$sa[i]$填的字符一定比$sa[i+1]$小


#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) rak[sa[i]=read()]=i;
	ans[sa[1]] = 'a';
	for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
	if (ans[n] <= 'z') printf("%s",ans+1);
	else puts("-1");
	return 0;

22 thoughts to “【BZOJ 4319】[CERC2008] Suffix Reconstruction”

  1. Howdy, i read your blog from time to time and i own a similar one
    and i was just wondering if you get a lot of spam comments?
    If so how do you stop it, any plugin or anything you can advise?
    I get so much lately it’s driving me insane so any support is very much appreciated.

  2. Very nice post. I just stumbled upon your blog and wished to say that I have
    truly enjoyed browsing your blog posts. After all I’ll be subscribing to your
    rss feed and I hope you write again very soon!

  3. Hey would you mind stating which blog platform you’re using?
    I’m going to start my own blog in the near future
    but I’m having a tough time selecting between BlogEngine/Wordpress/B2evolution and Drupal.

    The reason I ask is because your design and style seems different then most blogs and I’m looking
    for something completely unique. P.S My apologies for getting off-topic
    but I had to ask!

  4. We stumbled over here from a different web address and thought I should check things out.

    I like what I see so now i am following you. Look forward to finding out
    about your web page for a second time.

  5. Hey there! Quick question that’s completely off topic. Do you
    know how to make your site mobile friendly? My blog looks weird when viewing from
    my iphone4. I’m trying to find a theme or plugin that might be able
    to fix this problem. If you have any recommendations, please
    share. With thanks!

  6. Nice blog here! Also your site loads up very fast!
    What web host are you using? Can I get your affiliate
    link to your host? I wish my website loaded up as fast as yours lol

  7. Hi! This is my first comment here so I just wanted to give a quick shout out and say I truly enjoy
    reading your articles. Can you suggest any other blogs/websites/forums that
    cover the same subjects? Thanks a lot!

  8. What’s up it’s me, I am also visiting this web page regularly,
    this web site is in fact good and the viewers are truly sharing
    nice thoughts.

  9. Heya i’m for the first time here. I found this board and
    I find It really useful & it helped me out much. I hope to give something back and aid others like you
    aided me.

  10. Good blog you have got here.. It’s hard to find high quality writing like yours nowadays.
    I truly appreciate individuals like you! Take care!!

  11. You made some decent points there. I looked on the net to find out more about the issue and found most people will go along with your views
    on this website.

  12. Thanks a lot for sharing this with all people you actually recognise what you’re speaking about!

    Bookmarked. Kindly additionally talk over with my site =).
    We may have a link exchange arrangement between us

  13. Everyone loves what you guys tend to be up too. This kind of clever
    work and reporting! Keep up the wonderful works guys I’ve added you guys to our blogroll.

  14. Thanks , I’ve recently been searching for information about this topic for
    a long time and yours is the best I’ve came upon till now.
    However, what concerning the conclusion? Are you certain concerning the supply?

Leave a Reply

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