BZOJ 2754 喵星球上的点名（后缀数组）

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2754

题意：给出n个字典串，m个询问串。输出每个询问串出现在多少个字典串中。最后输出每个字典串中含有多少个询问串。

思路：将所有字典串和所有询问串连在一起求sa和h数组。统计时对于每个询问串，设长度为len，向前向后扫一下h值大于等于len的区间。然后在这个区间中看有多少个字典串，就是这个询问串的答案，同时将这些字典串包含询问串个数加1。

int r[N],sa[N],wa[N],wb[N],wd[N],rank[N],h[N];

int cmp(int *r,int a,int b,int len)
{
return r[a]==r[b]&&r[a+len]==r[b+len];
}

void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
FOR0(i,m) wd[i]=0;
FOR0(i,n) wd[x[i]=r[i]]++;
FOR1(i,m-1) wd[i]+=wd[i-1];
FORL0(i,n-1) sa[--wd[x[i]]]=i;
for(j=1,p=1;p<n;j<<=1,m=p)
{
p=0;
FOR(i,n-j,n-1) y[p++]=i;
FOR0(i,n) if(sa[i]>=j) y[p++]=sa[i]-j;
FOR0(i,m) wd[i]=0;
FOR0(i,n) wd[x[i]]++;
FOR1(i,m-1) wd[i]+=wd[i-1];
FORL0(i,n-1) sa[--wd[x[y[i]]]]=y[i];
t=x;x=y;y=t;p=1;x[sa[0]]=0;
FOR1(i,n-1) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void calHeight(int *r,int *sa,int n)
{
int i,j,k=0;
FOR1(i,n) rank[sa[i]]=i;
FOR0(i,n)
{
if(k) k--;
j=sa[rank[i]-1];
while(i+k<n&&j+k<n&&r[i+k]==r[j+k]) k++;
h[rank[i]]=k;
}
}

int b[N];
int n,m,M;
set<int> S;
set<int>::iterator it;
int c[N],d[N];
int ans[N],ans1[N];

void deal(int n)
{
int i,j,L,R,len;
for(i=1;i<=n;i++) if(d[sa[i]])
{
S.clear(); len=c[d[sa[i]]];
for(j=i;j>=2;j--) if(h[j]<len) break;
L=j;
for(j=i+1;j<=n;j++) if(h[j]<len) break;
R=j-1;
for(j=L;j<=R;j++) if(sa[j]<=M) S.insert(b[sa[j]]);
ans[d[sa[i]]]=SZ(S);
for(it=S.begin();it!=S.end();it++)
{
ans1[*it]++;
}
}
}

int main()
{
RD(n,m);
int i,j,x,y,t=10002,p=0;
FOR1(i,n)
{
RD(x);
FOR1(j,x) RD(y),r[p]=y+1,b[p++]=i;
r[p]=t++;
b[p++]=0;
RD(x);
FOR1(j,x) RD(y),r[p]=y+1,b[p++]=i;
r[p]=t++;
b[p++]=0;
}
M=p-1;
FOR1(i,m)
{
RD(x); c[i]=x;
FOR1(j,x)
{
if(j==1) d[p]=i;
RD(y),r[p]=y+1,b[p++]=i;
}
if(i<m) r[p]=t++,b[p++]=0;
}
r[p]=0;
da(r,sa,p+1,t);
calHeight(r,sa,p);
deal(p);
FOR1(i,m) PR(ans[i]);
FOR1(i,n-1) printf("%d ",ans1[i]);
PR(ans1[i]);
}

巴特西

BZOJ 2754 喵星球上的点名（后缀数组）

最新文章

热门文章