*玄关*求助!字典树查询输出0
查看原帖
*玄关*求助!字典树查询输出0
1399216
_Gloaming_楼主2024/8/15 10:12
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
struct node
{
    int end,sum;//以这个结点的结尾 经过这个结点的条数
    int s[2];
}t[N];
int n,m,k,a[N];
void insert(int k)
{
    int cnt=1;//每次从顶端开始
    for(int i=1;i<=k;i++)
        cin>>a[i];
    for(int i=1;i<=k;i++)
    {
        if(t[cnt].s[a[i]]==0)//如果没有走过
            t[cnt].s[a[i]]=++cnt;//第几个被走过
        cnt=t[cnt].s[a[i]];//子结点
        t[cnt].sum++;
    }
    t[cnt].end++;
}
int find(int k)
{
    int cnt=1,ans=0;
    for(int i=1;i<=k;i++)
        cin>>a[i];
    for(int i=1;i<=k;i++)
    {
        if(t[cnt].s[a[i]])
        {
            cnt=t[cnt].s[a[i]];
            ans+=t[cnt].end; 
        }
        else
            return ans;     
    }
    ans+=t[cnt].sum-t[cnt].end;
    return ans;
}
int main()
{
    cin>>m>>n;
    memset(t,0,sizeof(t));
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        insert(k);
    }
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        cout<<find(m)<<"\n";
    }
    return 0;
}
2024/8/15 10:12
加载中...