题目

难点：
对于前缀的计算要理解清楚
比如对于暗号：11，有相同前缀的信息既有1也有110

我的处理

对于一个信息串，每一位上的cnt[]都++
然后在对暗号进行判断时

if(i==len-1) res+=cnt[p];
else res=res+cnt[p]-cnt[son[p][0]]-cnt[son[p]

如果当前字符i不是暗号的最后一个字母，那么当前cnt就要减去两个子串的cnt(才是单独的以字符i为结尾的子串数量)
如果i是暗号的最后一个字符了，那就直接加上cnt[]

题解记录

区分两种记录：
经过该节点的字符串数 和 以该节点为尾巴的字符串数

我的题解相当于没有只记录了“经过该节点的字符串数”，然后通过这个算出了“以该节点为尾巴的字符串数”

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+7;
const int M=1e+7;
int son[N][2];
int cnt[N];
int idx;
int m,n;
int mes[M],len;

void insert(int mes[],int len)
{
    //注意mes的每个位上对应的数字的cnt都要++
    int p=0;
    for(int i=0;i<len;i++){
        int u=mes[i];
        if(son[p][u]==0) son[p][u]=++idx;
        p=son[p][u];
        cnt[p]++;
    }
}

int query(int mes[],int len)
{
    int p=0;
    int res=0;
    for(int i=0;i<len;i++){
        int u=mes[i];
        if(son[p][u]==0){
            break;
        }
        p=son[p][u];
        if(i==len-1) res+=cnt[p];
        else res=res+cnt[p]-cnt[son[p][0]]-cnt[son[p][1]];
    }
    return res;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++){
        //第i条信息
        scanf("%d",&len);
        for(int i=0;i<len;i++) scanf("%d",&mes[i]);
        insert(mes,len);
    }
    for(int i=0;i<n;i++){
        //第i次询问
        scanf("%d",&len);
        for(int i=0;i<len;i++) scanf("%d",&mes[i]);
        printf("%d\n",query(mes,len));
    }
    return 0;
}