bzoj 2754 [SCOI2012]喵星球上的点名（后缀数组）

时间：2022-06-12 07:24:13

【题目链接】

　　http://www.lydsy.com/JudgeOnline/problem.php?id=2754

【题意】

　　每只喵有名姓，如果被老师点到名或姓的子串都要答道，但每只喵一次点名只答一次，问每次有多少只喵答道，以及每只喵答道多少次。

【思路】

后缀数组

将所有的串连起来，包括姓名和询问。处理出rank[],sa[],height[]，通过rank确定一个询问的位置，然后在height上左右各扫一下，统计即可。flag对同一只标记，kase是时间戳（也算知道叫什么了=-=）

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N = *1e5+1e2;

 int s[N];

 int sa[N],height[N],rank[N],t[N],t2[N],c[N];

 void build_sa(int m,int n) {

     int i,k,*x=t,*y=t2;

     for(i=;i<m;i++) c[i]=;

     for(i=;i<n;i++) c[x[i]=s[i]]++;

     for(i=;i<m;i++) c[i]+=c[i-];

     for(i=n-;i>=;i--) sa[--c[x[i]]]=i;

     for(k=;k<=n;k<<=) {

         int p=;

         for(i=n-k;i<n;i++) y[p++]=i;

         for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

         for(i=;i<m;i++) c[i]=;

         for(i=;i<n;i++) c[x[y[i]]]++;

         for(i=;i<m;i++) c[i]+=c[i-];

         for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];

         swap(x,y);

         p=; x[sa[]]=;

         for(i=;i<n;i++)

             x[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]? p-:p++;

         if(p>=n) break;

         m=p;

     }

 }

 void get_height(int n) {

     int i,j,k=;

     for(i=;i<n;i++) rank[sa[i]]=i;

     for(i=;i<n;i++) {

         if(k) k--;

         j=sa[rank[i]-];

         while(s[i+k]==s[j+k]) k++;

         height[rank[i]]=k;

     }

 }

 int n,m;

 int flag[N],kase,ans[N],from[N],que[N],length[N];

 void read(int& x) {

     char c=getchar(); int f=; x=;

     while(!isdigit(c)){if(c=='-')f=-; c=getchar();}

     while(isdigit(c)) x=x*+c-'',c=getchar();

     x*=f;

 }

 int main() {

     memset(from,-,sizeof(from));

     read(n),read(m);

     int x,len=;

     for(int i=;i<n;i++) {

         read(x);

         for(int j=;j<x;j++)

             read(s[len]),from[len++]=i;

         s[len++]=;

         read(x);

         for(int j=;j<x;j++)

             read(s[len]),from[len++]=i;

         s[len++]=;

     }

     for(int i=;i<m;i++) {

         read(x);

         que[i]=len; length[i]=x;

         for(int j=;j<x;j++)

             read(s[len++]);

         s[len++]=;

     }

     build_sa(,len);

     get_height(len);

     for(int i=;i<m;i++) {

         int p=rank[que[i]],tot=;

         ++kase;

         while(height[p]>=length[i]) {

             if(from[sa[p-]]!=-)

                 if(flag[from[sa[p-]]]!=kase) {

                     flag[from[sa[p-]]]=kase;

                     ++tot;

                     ++ans[from[sa[p-]]];

                 }

             p--;

             if(!p) break;

         }

         p=rank[que[i]];

         while(height[p+]>=length[i]) {

             if(from[sa[p+]]!=-)

                 if(flag[from[sa[p+]]]!=kase) {

                     flag[from[sa[p+]]]=kase;

                     ++tot;

                     ++ans[from[sa[p+]]];

                 }

             p++;

             if(p==len) break;

         }

         printf("%d\n",tot);

     }

     printf("%d",ans[]);

     for(int i=;i<n;i++) printf(" %d",ans[i]);

 }

相关文章