迷之好奇 (sdut3039)

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

迷之好奇,c++tle用c就a了,迷之好奇

和字典树一样,只不过倒着建树倒着查找即可

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int top,len;
struct node
{
    int data;
    int next[10];
};
node tree[10000];
int create_kong()
{
    tree[top].data=0;
    memset(tree[top].next,-1,sizeof(tree[top].next));
    top++;
    return top-1;
}
void create(int root,char *a)
{
    int t;
    for(int i=len-1;i>=0;i--)
    {
        t=a[i]-'0';
        if(tree[root].next[t]==-1)
        {
            tree[root].next[t]=create_kong();
        }
        tree[root].data++;
        root=tree[root].next[t];
    }
    //tree[root].data--;
}
int serch(int root,char *a)
{
    int t;
    for(int i=len-1;i>=0;i--)
    {
        t=a[i]-'0';
        if(tree[root].next[t]==-1)return 0;
        root=tree[root].next[t];
    }
    return tree[root].data;
}
int main()
{
    char a[100010];
    int n,l;
    while(~scanf("%d",&n))
    {
        top=0;
        int root;
        root=create_kong();
        while(n--)
        {
            scanf("%s",a);
            len=strlen(a);
            create(root,a);
        }
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",a);
            len=strlen(a);
            l=serch(root,a);
            printf("%d\n",l);
        }
    }
    return 0;

发表评论

电子邮件地址不会被公开。 必填项已用*标注