[USACO08DEC]Secret Message G - 洛谷
题意
贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．
信息是二进制的，共有 MM（1 \le M \le 500001≤M≤50000）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 ii 条二进制信息的前 b_ibi?（l \le b_i \le 10000l≤bi?≤10000）位，他同时知道，奶牛使用 NN（1 \le N \le 500001≤N≤50000）条暗号．但是，他仅仅知道第 jj 条暗号的前 c_jcj?（1 \le c_j \le 100001≤cj?≤10000）位。
对于每条暗号 jj，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。
在输入文件中，位的总数（即 \sum b_i + \sum c_i∑bi?+∑ci?）不会超过 500000。
输入输出样例
输入
4 5 3 0 1 0 1 1 3 1 0 0 3 1 1 0 1 0 1 1 2 0 1 5 0 1 0 0 1 2 1 1
输出
1 3 1 1 2
题解：
典型的字典树统计题。
建树，在这串数列中走过的路径中的sum+1，num代表有num个串经过这个节点。
当一个串插完以后，在当前节点（即该串的最后一个数字）的cnt上+1，cnt代表有cnt个串在这个节点终结。
注意可能会有重复的信息，也就是说可能会有多条信息在同一个节点终结，所以这里的cnt是数字而不是布尔型。
然后读入待查询的信息，就像普通字典树查询一样地往下走，一边走一边把沿途的end值加起来。
如果完全走到尾，就减cnt，加num，意为加上以该串为前缀的数量，同时减掉刚好一模一样的串。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const int maxn=1e6+10;
int n,m,k,tot,num[maxn],cnt[maxn];
int tre[maxn][2];
char s[maxn];
bool f=1;
void _add(char s[],int len){int now=0;for(int i=0;i<len;i++){int tep=s[i]-'0';if(!tre[now][tep]){tre[now][tep]=++tot;}now=tre[now][tep];num[now]++;}cnt[now]++;return;
}
int ask(char s[],int len){int now=0,ans=0;for(int i=0;i<len;i++){int tep=s[i]-'0';if(tre[now][tep]) {now=tre[now][tep];ans+=cnt[now];}else break;if(i==len-1){ans+=num[now]-cnt[now];break;}}return ans;
}
signed main(){fastm=read();n=read();for(int i=1;i<=m;i++){k=read();for(int i=0;i<k;i++) s[i]=read();_add(s,k); }for(int i=1;i<=n;i++){k=read();for(int i=0;i<k;i++) s[i]=read();printf("%lld\n",ask(s,k));}
}