程序员人生 网站导航

【BZOJ2754】【SCOI2012】喵星球上的点名 后缀数组优化暴力

栏目:php教程时间:2015-02-02 08:54:23

转载请注明出处谢谢:http://blog.csdn.net/vmurder/article/details/42963375

题意:

那个输入中每一个串先是1个长度然后才是串。

然后如果某猫姓名abcd・efgh,那末点名abc,bcd,fg等都是好使的,但是cde就不行。


然后输入姓名时格式为1行

a a个数,b b个数。

A表示姓,B表示名。


题解:

直接暴力枚举每一个点名是哪些的子串,

然后我们发现可以用后缀数组来优化这个事情~~


时间复杂度是不准确的,也就是说可以被卡成TLE,但是大家都没有写正解,

所以应当不会有丧(Po)心(Po)病(Q)狂(Q)者(Q)去Hack这道题的。


所以安心乱弄吧。

代码:

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 501000 #define M 50100 #define inf 10100 using namespace std; int s[N],len; int sa[N],rank[N],height[N]; int cnt[N],val[N],_val[N]; int stk[N],top; int n,m,crs[N]; struct QUERY { int n,s; }Query[M]; int ans[M],vis[M]; void Input() { int i,j,k,fengefu=inf; scanf("%d%d",&n,&m); // 为了不多匹配,所以分隔符都不1样 for(i=1;i<=n;i++) // 读入每一个喵的姓名,中间有分隔符。 { for(scanf("%d",&k);k--;) { crs[len]=i; scanf("%d",&s[len++]); } s[len++]=++fengefu; for(scanf("%d",&k);k--;) { crs[len]=i; scanf("%d",&s[len++]); } s[len++]=++fengefu; } for(i=1;i<=m;i++) // 输入每一个点名 { scanf("%d",&Query[i].n); Query[i].s=len; for(j=1;j<=Query[i].n;j++) scanf("%d",&s[len++]); s[len++]=++fengefu; } } inline bool cmp(int x,int y,int hl) {return val[x]==val[y]&&((x+hl>=len&&y+hl>=len)||(x+hl<len&&y+hl<len&&val[x+hl]==val[y+hl]));} void SA(int lim=256) { int i,j,k,hl; for(i=0;i<lim;i++)cnt[i]=0; for(i=0;i<len;i++)cnt[val[i]=s[i]]++; for(i=1;i<lim;i++)cnt[i]+=cnt[i⑴]; for(i=len⑴;i>=0;i--)sa[--cnt[val[i]]]=i; for(k=0;;k++) { top=0,hl=1<<k; for(i=0;i<len;i++)if(sa[i]+hl>=len)stk[++top]=sa[i]; for(i=0;i<len;i++)if(sa[i]>=hl)stk[++top]=sa[i]-hl; for(i=0;i<lim;i++)cnt[i]=0; for(i=0;i<len;i++)cnt[val[i]]++; for(i=1;i<lim;i++)cnt[i]+=cnt[i⑴]; for(i=len;i;i--)sa[--cnt[val[stk[i]]]]=stk[i]; for(i=lim=0;i<len;lim++) { for(j=i;j<len⑴&&cmp(sa[j],sa[j+1],hl);j++); for(;i<=j;i++)_val[sa[i]]=lim; } for(i=0;i<len;i++)val[i]=_val[i]; if(lim==len)break; } for(i=0;i<len;i++)rank[sa[i]]=i; for(k=i=0;i<len;i++) { if(k)k--; if(!rank[i])continue; while(s[i+k]==s[sa[rank[i]⑴]+k])k++; height[rank[i]]=k; } } void Work() { int i,j,k; int l,r,res; for(i=1;i<=m;i++){ l=r=rank[Query[i].s]; while(height[l]>=Query[i].n)l--; while(height[r]>=Query[i].n)r++; r--,res=0; for(j=l;j<=r;j++){ if(crs[sa[j]]){ if(vis[crs[sa[j]]]!=i){ vis[crs[sa[j]]]=i; res++; ans[crs[sa[j]]]++; } } } printf("%d ",res); } for(i=1;i<=n;i++) { printf("%d",ans[i]); if(i!=n)putchar(' '); } } int main() { freopen("test.in","r",stdin); Input(); SA(200000); Work(); return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐