洛谷 2922 BZOJ 1590 [USACO08DEC]秘密消息Secret Message

【题意概述】

　　给出n个01串组成的字典和m个询问，每次询问某个01串和多少个字典中的串有相同的前缀。（前缀长度是两串中较小的部分）

【题解】

　　直接上Trie树即可。树上每个节点记录两个信息：这个节点有多少个串经过，这个节点是多少个串的结尾。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 #define rg register

 #define N 500010

 using namespace std;

 int n,m,a[N][],now,ans,tot;

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 int main(){

     memset(a,,sizeof(a));

     n=read(); m=read();

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

         int x=read(); now=;

         while(x--){

             int y=read();

             if(a[now][y]>) now=a[now][y];

             else a[now][y]=++tot,now=a[now][y];

             a[now][]++;

         }

         a[now][]++;

     }

     while(m--){

         int x=read(); bool ok=; ans=now=;

         while(x--){

             int y=read();

             if(a[now][y]&&ok){

                 now=a[now][y];

                 if(a[now][]) ans+=a[now][];

             }

             else ok=;

         }

         if(ok) ans+=a[now][]-a[now][];

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

     }

     return ;

 }