sdut oj 迷之好奇（字典树）

心已赠人 2021-11-12 00:10 188阅读 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

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

Sample Input

3  
12345  
66666  
12356  
3  
45  
12345  
356

Sample Output

1  
0  
1

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct node
    { 
        int id;
        struct node *next[10];
        int f;
    } NODE;
    
    NODE T[1000000];
    int top;
    
    NODE *creat()
    { 
        NODE *p;
        int i;
        p = &T[top++];
        for(i=0; i<=9; i++)
        { 
            p->next[i]=NULL;
        }
        p->id=0;
        p->f=0;
        return p;
    }
    
    void insertt(NODE *root,char s[])
    { 
        NODE *p=root;
        int i;
        for(i=0; s[i]!='\0'; i++)
        { 
            int x=s[i]-'0';
            if(p->next[x]!=NULL)
            { 
                p=p->next[x];
            }
            else
            { 
                p->next[x]=creat();
                p=p->next[x];
            }
            p->id++;
        }
        p->f++;
    }
    
    int check(NODE *t,char s[])
    { 
        NODE *p=t;
        int i;
        for(i=0; s[i]!='\0'; i++)
        { 
            int x=s[i]-'0';
            if(p->next[x]!=NULL)
            { 
                p=p->next[x];
            }
            else
            { 
                return 0;
            }
        }
        int k=p->id;
        if(p->f!=0)
            k-=p->f;
        return k;
    }
    
    int main()
    { 
        int i,j,n,m;
        char s[100010];
        char s1[100010];
        while(~scanf("%d",&n))
        { 
            NODE *t;
            top=0;
            t=(NODE *)malloc(sizeof(NODE));
            t=creat();
            for(i=0; i<n; i++)
            { 
                scanf("%s",s1);
                int len=strlen(s1);
                for(j=0; j<len; j++)
                { 
                    s[j]=s1[len-1-j];
                }
                s[len]='\0';
                insertt(t,s);
            }
            scanf("%d",&m);
            for(i=0; i<m; i++)
            { 
                scanf("%s",s1);
                int len=strlen(s1);
                for(j=0; j<len; j++)
                { 
                    s[j]=s1[len-1-j];
                }
                s[len]='\0';
                int k=check(t,s);
                printf("%d\n",k);
            }
        }
        return 0;
    }