【数据范围】
对于30%的数据，保证：
1<=N,M<=1000，喵星人的名字总长不超过4000，点名串的总长不超过2000。
对于100%的数据，保证：
1<=N<=20000，1<=M<=50000，喵星人的名字总长和点名串的总长分别不超过100000，保证喵星人的字符串中作为字符存在的数不超过10000。
#include<cstdio> #include<cstring> #define p 29 #define debug(x) printf("%I64u ",x); using namespace std; typedef unsigned long long UL; const int N=1005; UL chk,Q[N<<1],ts[N<<2],hs[N][N<<2],a[N<<1],base[N]; int n,m,xlen[2][N<<1],len[N<<1]; int Ans[N<<1],ans[N<<1]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } UL query(int x,int y,int id){ return hs[id][y]-hs[id][x-1]*base[y-x+1]; } int main(){ freopen("name.in","r",stdin); freopen("name.out","w",stdout); n=read();m=read(); for(int i=1,x1;i<=n;i++){ x1=read();xlen[0][i]=x1;hs[i][0]=0; for(int j=1;j<=x1;j++) a[j]=read(); for(int j=0;j<=x1;j++) ts[j]=0; for(int j=1;j<=x1;j++) ts[j]=ts[j-1]*p+a[j]; for(int j=1;j<=x1;j++) hs[i][j]=ts[j]; x1=read();xlen[1][i]=x1;hs[i][xlen[0][i]+1]=0; for(int j=1;j<=x1;j++) a[j]=read(); for(int j=0;j<=x1;j++) ts[j]=0; for(int j=1;j<=x1;j++) ts[j]=ts[j-1]*p+a[j]; for(int j=1;j<=x1;j++) hs[i][j+xlen[0][i]+1]=ts[j]; } for(int i=1,x1;i<=m;i++){ x1=read();len[i]=x1; for(int j=1;j<=x1;j++) a[j]=read(); for(int j=1;j<=x1;j++) Q[i]=Q[i]*p+a[j]; } base[0]=1; for(int i=1;i<=100;i++) base[i]=base[i-1]*p; for(int i=1;i<=m;i++){//点名的串 for(int k=1;k<=n;k++){//姓和名两个串 int flag=0; for(int j=1;j<=xlen[0][k]-len[i]+1;j++){ chk=query(j,j+len[i]-1,k); if(chk==Q[i]){ Ans[i]++;ans[k]++;flag=1;break; } } if(flag) continue; for(int j=1;j<=xlen[1][k]-len[i]+1;j++){ chk=query(j+xlen[0][k]+1,j+xlen[0][k]+len[i],k); if(chk==Q[i]){ Ans[i]++;ans[k]++;break; } } } } for(int i=1;i<=m;i++) printf("%d\n",Ans[i]); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
考试的时候，直觉告诉我:可能是AC自动机（“子串”一词）
然，离线把询问串见trie，然后对每个名字串进行匹配。（反着搞）
O(20000*100000)
写出来我就后悔了。（样例还没过去）
算了，30分，暴力hash。
试后，网上正解fail数，反着的AC自动机（我去~真跟AC自动机有关~后悔当时没多想想）
看了半天，fail树弃疗了（感觉他的性质好神奇）
民间还是有向我一样的蒟蒻的，把所有名字串连起来，用后缀数组询问子串。
又有M组询问（好烦人~MO DEI KEI），上莫队，离线处理，至此bingo
#include<cstdio> #include<cstring> using namespace std; const int N=5e5+7,M=5e4+7; int n,m,len,maxx,sa[N],tsa[N],rank[N],trank[N],h[N],c[N]; int fengefu,crs[N],s[N],ans[N];int vis[M]; struct no{int n,s;}Q[M];char st[N]; void init(){ fengefu=10100; scanf("%d%d",&n,&m); for(int i=1,k;i<=n;i++){ scanf("%d",&k); for(int j=1;j<=k;j++){ crs[++len]=i; scanf("%d",&s[len]);s[len]++; } s[++len]=++fengefu; scanf("%d",&k); for(int j=1;j<=k;j++){ crs[++len]=i; scanf("%d",&s[len]);s[len]++; } s[++len]=++fengefu; } for(int i=1;i<=m;i++){ scanf("%d",&Q[i].n);Q[i].s=len; for(int j=1;j<=Q[i].n;j++){ scanf("%d",&s[++len]);s[len]++; } s[++len]=++fengefu; } } void DA(int maxx=256){ int p; memset(c,0,sizeof c); for(int i=1;i<=len;i++) c[rank[i]=s[i]]++; for(int i=2;i<=maxx;i++) c[i]+=c[i-1]; for(int i=len;i;i--) sa[c[rank[i]]--]=i; trank[sa[1]]=p=1; for(int i=2;i<=len;i++){ if(rank[sa[i]]!=rank[sa[i-1]]) p++; trank[sa[i]]=p; } for(int i=1;i<=len;i++) rank[i]=trank[i]; for(int k=1;p<len;k<<=1,maxx=p){ p=0; for(int i=len-k+1;i<=len;i++) tsa[++p]=i; for(int i=1;i<=len;i++) if(sa[i]>k) tsa[++p]=sa[i]-k; memset(c,0,sizeof c); for(int i=1;i<=len;i++) trank[i]=rank[tsa[i]]; for(int i=1;i<=len;i++) c[trank[i]]++; for(int i=2;i<=maxx;i++) c[i]+=c[i-1]; for(int i=len;i;i--) sa[c[trank[i]]--]=tsa[i]; trank[sa[1]]=p=1; for(int i=2;i<=len;i++){ if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++; trank[sa[i]]=p; } for(int i=1;i<=len;i++) rank[i]=trank[i]; } for(int i=1,k=0;i<=len;i++){ int j=sa[rank[i]-1]; while(s[i+k]==s[j+k]) k++; h[rank[i]]=k;if(k>0) k--; } } void work(){ for(int i=1,l,r,res;i<=m;i++){ l=r=rank[Q[i].s+1]; while(h[l]>=Q[i].n) l--; while(h[r]>=Q[i].n) r++; r--; res=0; for(int 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\n",res); } for(int i=1;i<=n;i++) printf("%d ",ans[i]); } int main(){ freopen("name.in","r",stdin); freopen("name.out","w",stdout); init(); DA(200000); work(); return 0; }
原文：http://www.cnblogs.com/shenben/p/6421802.html
