P2922 [USACO08DEC]Secret Message G （字典树 trie）

[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，意为加上以该串为前缀的数量，同时减掉刚好一模一样的串。

代码：

#includeusing 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'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)); }}