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]);
}