迷之好奇

野性酷女 2022-07-12 06:40 155阅读 0赞

#### Problem Description ####

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

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

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

#### Input ####

多组输入。

对于每组数据

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

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

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

接下来的m行。

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

#### Output ####

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

#### Example Input ####

3
    12345
    66666
    12356
    3
    45
    12345
    356

#### Example Output ####

1
    0
    1

#include<stdio.h>
    #include<string.h>
    #define maxn 600000
    #define maxc 10
    typedef struct node
    {
        int cnt;
        struct node *next[maxc];
    }trietree;
    
    int sum;
    trietree trie[maxn];
    int top=-1;
    
    trietree * create()
    {
        int i;
        trietree * t;
        t=&trie[++top];
        t->cnt=0;
        for(i=0;i<maxc;i++)
        {
            t->next[i]=NULL;
        }
        return t;
    }
    
    trietree * init()
    {
        top=-1;
        return (create());
    }
    
    void insert(trietree * t,char str[],int len)
    {
        int i,id;
        trietree * p=t;
        for(i=len-1;i>=0;i--)
        {
            id=str[i]-'0';
            if(!p->next[id])
            {
                p->next[id]=create();
            }
            p=p->next[id];
            p->cnt++;
        }
        p->cnt--;
    }
    
    int find(trietree * t,char str[],int len)
    {
        int i,id,sum;
        trietree * p=t;
        for(i=len-1;i>=0;i--)
        {
            id=str[i]-'0';
            if(!p->next[id])
            {
                return 0;
            }
            p=p->next[id];
        }
        for(i=0;i<maxc;i++)
        {
            if(p->next[i]!=NULL)
            {
                break;
            }
        }
        if(i==maxc)
        {
            return 0;
        }
        else
        {
            return p->cnt;
        }
    }
    
    int main()
    {
        char str[8];
        int n,m,i,len,flag;
        trietree * tree;
        while(scanf("%d",&n)!=EOF)
        {
            tree=init();
            while(n--)
            {
                scanf("%s",str);
                len=strlen(str);
                insert(tree,str,len);
            }
            scanf("%d",&m);
            while(m--)
            {
                flag=0;
                scanf("%s",str);
                len=strlen(str);
                flag=find(tree,str,len);
                if(flag)
                {
                    printf("%d\n",flag);
                }
                else
                {
                    printf("0\n");
                }
            }
        }
        return 0;
    }