首页 > 代码库 > BZOJ2251: [2010Beijing Wc]外星联络
BZOJ2251: [2010Beijing Wc]外星联络
2251: [2010Beijing Wc]外星联络
Time Limit: 30 Sec Memory Limit: 256 MBSubmit: 365 Solved: 191
[Submit][Status]
Description
小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻
找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星
人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高
低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在
其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以
他希望找到他接受到的 01 串中所有重复出现次数大于 1 的子串。但是他收到的
信号串实在是太长了，于是，他希望你能编一个程序来帮助他。
Input
输入文件的第一行是一个整数N ，代表小 P 接收到的信号串的长度。
输入文件第二行包含一个长度为N 的 01 串，代表小 P 接收到的信号串。
Output
输出文件的每一行包含一个出现次数大于1 的子串所出现的次数。输出的顺
序按对应的子串的字典序排列。
Sample Input
7
1010101
1010101
Sample Output
3
3
2
2
4
3
3
2
2
3
2
2
4
3
3
2
2
HINT
对于 100%的数据，满足 0 <=? ? N <=3000
Source
题解：
终于1A了一道题。。。
考虑到以sa[i]开头的本质不同的字串的数目只有 n-sa[i]-h[i]个，而如果按字典序来就从sa[1]-sa[n]即可
然后求一个字串出现的次数，只要在该字串第一次出现的时候 暴力像后匹配即可，
我想到了一个优化，从长的向短匹配，这样长的能匹配到的地方短的也能匹配到，所以能充分利用原来计算过的信息。
可是还是没跑进第一页T_T
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 5000+100 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int a[maxn],b[maxn],sa[maxn],wa[maxn],wb[maxn],wr[maxn],h[maxn],rank[maxn]; 61 int n,m,tot; 62 inline bool cmp(int *r,int a,int b,int l) 63 { 64 return r[a]==r[b]&&r[a+l]==r[b+l]; 65 } 66 void da(int n,int m) 67 { 68 int *x=wa,*y=wb,*t; 69 for0(i,m)wr[i]=0; 70 for0(i,n)wr[x[i]=a[i]]++; 71 for1(i,m)wr[i]+=wr[i-1]; 72 for3(i,n,0)sa[--wr[x[i]]]=i; 73 for(int j=1,p=1;p<=n;j<<=1,m=p) 74 { 75 p=0;int i; 76 for2(i,n-j+1,n)y[p++]=i; 77 for0(i,n)if(sa[i]>=j)y[p++]=sa[i]-j; 78 for0(i,m)wr[i]=0; 79 for0(i,n)wr[x[y[i]]]++; 80 for1(i,m)wr[i]+=wr[i-1]; 81 for3(i,n,0)sa[--wr[x[y[i]]]]=y[i]; 82 for(i=1,t=x,x=y,y=t,p=1,x[sa[0]]=0;i<=n;i++) 83 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 84 } 85 } 86 void geth(int n) 87 { 88 for1(i,n)rank[sa[i]]=i; 89 for(int i=0,j,k=0;i<n;h[rank[i++]]=k) 90 for(k?k--:0,j=sa[rank[i]-1];a[i+k]==a[j+k];k++); 91 } 92 93 int main() 94 95 { 96 97 freopen("input.txt","r",stdin); 98 99 freopen("output.txt","w",stdout);100 101 n=read();102 for1(i,n)103 {104 char ch=‘ ‘;105 while(ch!=‘0‘&&ch!=‘1‘)ch=getchar();106 a[i-1]=ch-‘0‘+1;107 }108 a[n]=0;109 da(n,3);110 geth(n);111 //for0(i,n)cout<<i<<‘ ‘<<sa[i]<<‘ ‘<<h[i]<<endl;112 for1(i,n-1)113 {114 int k=i+1;tot=0;115 for3(j,n-sa[i],h[i]+1)116 {117 while(h[k]>=j)k++;118 if(k!=i+1)b[++tot]=k-i;119 }120 for3(i,tot,1)printf("%d\n",b[i]);121 } 122 123 return 0;124 125 }
BZOJ2251: [2010Beijing Wc]外星联络
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。