2013年6月10日 13:02

BZOJ2251: [2010Beijing Wc]外星联络【后缀数组】

BZOJ

题意:给一个字符串。输出在原串中出现次数大于1的子串的出现次数。这些本质不同的子串按字典序大小排序输出次数。

一眼题?嗯。、后缀数组就行了、根据sa数组和height数组扫一遍。前后扫height数组。

反正n≤3000,没必要二分了。还要写rmq啥的多麻烦啊是吧、、然后就行了、感觉跑的蛮快的?

第一次加了fread和fwrite还变慢了、、

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2000005;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],height[maxn],sa[maxn];
char s[maxn],str[maxn];
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++;
    }
}inline void ch(char *r,int n){
    int i,j,k=0;
    for(i=0;i<n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
        for(k=max(k-1,0),j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}int main(){
    int n;  scanf("%d%s",&n,str);
    for(int i=0;i<n;i++)str[i]++;   str[n++]=0;
    da(str,sa,n,256);   ch(str,n);
    for(int i=1;i<n;i++){
        for(int j=height[i]+1;sa[i]+j<n;j++){
            int l,r;
            for(l=i;l>=0 && height[l]>=j;l--);
            for(r=i+1;r<=n && height[r]>=j;r++);
            if(r-l<=1)continue;
            printf("%d\n",r-l);
        }
    }return 0;
}

Comments(0)

Tags:

2013年6月09日 15:38

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

BZOJ

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

比如样例: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;
}

Comments(0)

Tags:

dzy493941464
Music
搜索
计数器
120320

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1