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

转载请注明出处谢谢: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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【BZOJ2754】【SCOI2012】喵星球上的点名 后缀数组优化暴力

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡