迷之好奇
Time Limit: 2000 ms Memory Limit: 65536 KiB
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 <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *next[26];
};
struct node a[1000000];
int top;
struct node *create_empty( )
{
int i;
struct node *root = &a[top++];
root->data = 0;
for(i=0; i<26; i++)
root->next[i] = NULL;
return root;
}
struct node *Insert ( struct node *root, int s )
{
struct node *p = root;
int i, t;
for( i=0; s > 0; i++ )
{
t = s % 10;
s = s / 10;
if( !p->next[t] )
p->next[t] = create_empty();
p = p->next[t];
p->data++; //每个数字都记录出现次数
}
p->data--; //最高位次数减一，去掉本身
return root;
}
int Find( struct node *root, int s )
{
struct node *p = root;
int i, t;
for( i=0; s>0; i++ )
{
t = s % 10;
s = s / 10;
if( !p->next[t] )
return 0;
p = p->next[t];
}
return p->data;
}
int main()
{
int n, m;
while( cin >> n )
{
int x, y;
top = 0;
struct node *root = create_empty();
while( n-- )
{
cin >> y;
root = Insert( root, y );
}
cin >> m;
while( m-- )
{
cin >> x;
cout << Find( root, x ) << endl;
}
}
return 0;
}