迷之好奇

蔚落 2022-08-18 02:28 118阅读 0赞

## 迷之好奇 ##

####  ####

##### Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

FF得到了一个有n个数字的集合。不要问我为什么，有钱，任性。

FF很好奇的想知道，对于数字x，集合中有多少个数字可以在x前面添加任意数字得到。

如，x = 123，则在x前面添加数字可以得到4123，5123等。

## 输入 ##

多组输入。

对于每组数据

首先输入n(1<= n <= 100000)。

接下来n行。每行一个数字y(1 <= y <= 100000)代表集合中的元素。

接下来一行输入m(1 <= m <= 100000),代表有m次询问。

接下来的m行。

每行一个正整数x(1 <= x <= 100000)。

## 输出 ##

对于每组数据，输出一个数字代表答案。

## 示例输入 ##

3
    12345
    66666
    12356
    3
    45
    12345
    356

## 示例输出 ##

1
    0
    1

## 提示 ##

## 来源 ##

zmx

## 示例程序 ##

#include<iostream>    
        #include<cstdio>    
        #include<cstring>    
        using namespace std;    
        struct node    
        {    
            int next[30],bj;    
        }q[9000000];    
        char s[64];    
        int top;    
        int init()    
        {    
            memset(q[top].next,-1,sizeof(q[top].next));    
            q[top].bj=0;    
            return top++;    
        }    
        void bu(int k,char *s)    
        {    
            int i,j,l;    
            l=strlen(s);    
            for(i=l-1;i>=0;i--)    
            {    
                j=s[i]-'0';    
                if(q[k].next[j]==-1)    
                {    
                    q[k].next[j]=init();    
                }    
                q[k].bj++;    
                k=q[k].next[j];    
            }    
        }    
        int  fi(int k,char *s)    
        {    
            int i,j,l;    
            l=strlen(s);    
            for(i=l-1;i>=0;i--)    
            {    
                j=s[i]-'0';    
                if(q[k].next[j]==-1)    
                {    
                    return 0;    
                }    
                k=q[k].next[j];    
            }    
            return q[k].bj;    
        }    
        int main()    
        {    
            int n,m,i,j,k;    
            ios::sync_with_stdio(false);    
            while(cin>>n&&n)    
            {    
                top=0;    
                int root=init();    
                while(n--)    
                {    
                    cin>>s;    
                    bu(root,s);    
                }    
                cin>>m;    
                while(m--)    
                {    
                    cin>>s;    
                    int p=fi(root,s);    
                    printf("%d\n",p);    
                }    
            }    
            return 0;    
        }