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

dzy posted @ 2013年6月10日 13:02 in BZOJ with tags BZOJ 字符串 后缀数组 , 2011 阅读

题意:给一个字符串。输出在原串中出现次数大于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;
}
Avatar_small
Emma 说:
2023年1月25日 18:52

The problem highlights the power of this data structure and how it can be used to efficiently solve complex problems. With the right approach, this problem can be real properties Peyton solved in a relatively short amount of time. While the problem may appear daunting at first, it can be tackled with patience, persistence and the use of the Suffix Array.

Avatar_small
li9.in 说:
2023年6月08日 20:40

people of all ages, as we plan to publish news divided into General, Political, Crime, Sports, Entertainment, Education, and World News categories.Our reporting team plans to provide the Education & Recruitment li9.in Update for all age groups and to present the actual picture of recent events through inside coverage. Our goal would be to meet the requirements.


登录 *


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