迷之好奇
Time Limit: 2000MS
Memory Limit: 65536KB
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
Hint
Author
zmx
#include <stdio.h>
#include <string.h>
struct node
{int isend; //是否结束int next[10];int num;
}L[5000000]; //静态分配内存
int top,n,m;
char a[20],b[20];
int creat() //创建新结点
{memset(L[top].next,-1,sizeof(L[top].next));L[top].isend = 0;L[top].num = 0;return top++;
}
int xiab(char c) // 求下标
{return c - '0';
}
void insert(int root,char *s) //插入
{int i,len = strlen(s);for(i = len-1;i >= 0;i--){if(L[root].next[xiab(s[i])] == -1){L[root].next[xiab(s[i])] = creat();}L[root].num++;root = L[root].next[xiab(s[i])];}L[root].isend = 1;
}
int search(int root,char *s)//查找
{int len = strlen(s);for(int i = len-1;i >= 0;i--){if(L[root].next[xiab(s[i])] == -1)return 0;root = L[root].next[xiab(s[i])];}return L[root].num;
}
int main()
{int i,j,root;while(scanf("%d",&n) != EOF){top = 0;root = creat();for(i = 0;i < n;i++){scanf("%s",a);insert(root,a);}scanf("%d",&m);for(i = 0;i <m;i++){scanf("%s",b);printf("%d\n",search(root,b));}}return 0;
}