迷之好奇
TimeLimit: 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>
int top;
struct node
{
int next[26];
int flag;
} st[5001000];
int creat()
{
memset(st[top].next,-1,sizeof(st[top].next));
st[top].flag=0;
return top++;
}
void insertt(int root,char*s)
{
int len=strlen(s);
for(int i=len-1; i>=0; i--)
{
int t=s[i]-'0';
if(st[root].next[t]==-1)
{
st[root].next[t]=creat();
}
st[root].flag++;
root=st[root].next[t];
}
}
int cmp(char *s,int root)
{
int len=strlen(s);
for(int i=len-1; i>=0; i--)
{
int t=s[i]-'0';
if(st[root].next[t]==-1)
{
return 0;
}
root=st[root].next[t];
}
return st[root].flag;
}
int main()
{
int n,m,root;
char s[101];
char s1[101];
while(~scanf("%d",&n))
{
top=0;
root=creat();
while(n--)
{
scanf("%s",s);
insertt(root,s);
}
scanf("%d",&m);
while(m--)
{
scanf("%s",s1);
printf("%d\n",cmp(s1,root));
}
}
return 0;
}
/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 388ms
Take Memory: 1396KB
Submit time: 2017-02-10 16:44:15
****************************************************/