BZOJ1692: [Usaco2007 Dec]队列变换【后缀数组】

dzy posted @ 2013年6月09日 15:38 in BZOJ with tags 字符串 后缀数组 bzoj , 1485 阅读

题意:给你一个字符串。每次取出第一个字符或最后一个字符,放到新的字符串(初始为空)后面。求最小字典序的新字符串。

比如样例:ACDBCB。按这样的顺序拿:头尾尾尾头尾。这样得到ABCBCD。可以证明没有比它字典序更小的了。

一开始我先YY了个很傻比的贪心。第一个字符和最后一个字符比较。取小的。然后O(n)扫一遍。(画外音:你煞笔啊、gold的题目就给你这么水掉啊!、、)本着这种态度很快就发现样例都过不了。先取出A、B。然后是取队头的C还是队尾的C呢。这时就发现光比较这一个字符的大小是不够的。要比较整个字符串和整个字符串反转过来的字符串的字典序大小,才能决定取哪个。

那么想到了什么呢?很明显就是后缀数组。

把这个字符串反转一遍接在原字符串后面,中间加一个分隔符(最好是小于'A'的,比如'@')。然后求出rank数组。

下标  0  1 2 3  4 5 6  7 8  9 10 11 12

字符  A C D B C B @ B C B D  C   A

那么维护两个指针,一个从0开始,一个从n+1(反转的字符串的起点)开始。比较rank的大小,每次取小的先输出。OK!

(fread、fwrite蛮好的、轻松rank3)



#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100000;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],sa[maxn],str[maxn];
char s[maxn],buf[maxn],*p=buf,buf2[maxn],*o=buf2;
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }for(i=0;i<n;i++)rank[sa[i]]=i;
}int main(){
    fread(p,1,maxn,stdin);  int t=0,n=0;
    while(*p<'0'||*p>'9')p++;
    while(*p>='0'&&*p<='9')n=n*10+*p++-48;
    for(int i=1;i<=n;i++){ 
        while(*p<'A'||*p>'Z')p++;
        s[t++]=*p++; 
    }s[t++]='A'-1;
    for(int i=n-1;~i;i--)   s[t++]=s[i];    s[t++]='\0';
    da(s,sa,t,256);
    int j=0,k=n+1,c=0;
    for(int i=1;i<=n;i++)str[c++]=rank[j]>rank[k]?k++:j++;
    for(int i=0;i<n;i++){
        if(i&&i%80==0)*o++='\n';
        *o++=s[str[i]];
    }fwrite(buf2,1,o-buf2,stdout);
    return 0;
}
Avatar_small
AP 2nd Inter Botany 说:
2022年9月08日 20:26

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 2nd Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.

Avatar_small
Emma 说:
2023年1月23日 19:54

Good to see the details shared here regarding the queue transformation, and real estate marketing Bethel suffix array details you have shared here. Actually, I am not much aware of this topic but for students, I think this one is the best platform for getting more ideas about it. Keep sharing more details over here.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter