字典树
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
遇到单词不认识怎么办? 查字典啊，已知字典中有n个单词，假设单词都是由小写字母组成。现有m个不认识的单词，询问这m个单词是否出现在字典中。
Input
含有多组测试用例。
第一行输入n，m (n>=0&&n<=100000&&m>=0&&m<=100000)分别是字典中存在的n个单词和要查询的m个单词.
紧跟着n行，代表字典中存在的单词。
然后m行，要查询的m个单词
n=0&&m=0 程序结束
数据保证所有的单词都是有小写字母组成，并且长度不超过10
Output
若存在则输出Yes，不存在输出No .
Sample Input
3 2
aab
aa
ad
ac
ad
0 0Sample Output
No
Yes内存限制，需要申请静态内存，用malloc, new 等申请动态内存是不行的
动态内存与静态内存的区别
1. 静态内存
静态内存是指在程序开始运行时由编译器分配的内存，它的分配是在程序开始编译时完成的，不占用CPU资源。
程序中的各种变量，在编译时系统已经为其分配了所需的内存空间，当该变量在作用域内使用完毕时，系统会
自动释放所占用的内存空间。
变量的分配与释放，都无须程序员自行考虑。
eg:
基本类型，数组
2. 动态内存
用户无法确定空间大小，或者空间太大，栈上无法分配时，会采用动态内存分配。
3. 区别
a) 静态内存分配在编译时完成，不占用CPU资源; 动态内存分配在运行时，分配与释放都占用CPU资源。
b) 静态内存在栈(stack)上分配; 动态内存在堆(heap)上分配。
c) 动态内存分配需要指针和引用类型支持，静态不需要。
d) 静态内存分配是按计划分配，由编译器负责; 动态内存分配是按需分配，由程序员负责。
Memory Limit Exceeded代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
node *next[26];
};
struct node *create_empty( )
{
int i;
struct node *root = new node;
root->data = 0;
for(i=0; i<26; i++)
root->next[i] = NULL;
return root;
}
struct node *Insert ( struct node *root, char *s )
{
struct node *p = root;
int i, t;
for( i=0; s[i]; i++ )
{
t = s[i] - 'a';
if( !p->next[t] )
p->next[t] = create_empty();
p = p->next[t];
}
p->data++;
return root;
}
int Find( struct node *root, char *s)
{
struct node *p = root;
int i, t;
for( i=0; s[i]; i++ )
{
t = s[i] - 'a';
if( !p->next[t] )
return 0;
p = p->next[t];
}
return p->data;
}
int main()
{
int n, m;
char word[11];
while( cin >> n >> m )
{
if( n==0 && m == 0 ) break;
struct node *root = create_empty();
while( n-- )
{
cin >> word;
root = Insert( root, word );
}
while( m-- )
{
cin >> word;
if( Find( root, word ))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
Accepted代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
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, char *s )
{
struct node *p = root;
int i, t;
for( i=0; s[i]; i++ )
{
t = s[i] - 'a';
if( !p->next[t] )
p->next[t] = create_empty(); //该字母未存过，申请空间
p = p->next[t]; //向后走
}
p->data++; //单词结束
return root;
}
int Find( struct node *root, char *s)
{
struct node *p = root;
int i, t;
for( i=0; s[i]; i++ )
{
t = s[i] - 'a';
if( !p->next[t] ) //单词中该字母未出现
return 0;
p = p->next[t];
}
return p->data;
}
int main()
{
int n, m;
char word[11];
while( cin >> n >> m )
{
if( n == 0 && m == 0 ) break;
top = 0;
struct node *root = create_empty();
//建立空树
while( n-- )
{
cin >> word;
root = Insert( root, word ); //将单词插入树中
}
while( m-- )
{
cin >> word;
if( Find( root, word ))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}原代码MLE了，估计评测姬又出了问题，贴一发MeiK的关于评测姬的内存测量问题
二次AC代码：把所有的链式操作全换成数组
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 500005;
struct node
{
int data;
int next[26];
};
node tree[N];
int top;
int create_empty( )
{
fill( tree[top].next, tree[top].next+26, 0 );
tree[top].data = 0;
return top++;
}
void Insert ( int root, char *s )
{
int i, t;
for( i=0; s[i]; i++ )
{
t = s[i] - 'a';
if( !tree[root].next[t] )
tree[root].next[t] = create_empty(); //该字母未存过，申请空间
root = tree[root].next[t]; //向后走
}
tree[root].data++; //单词结束
//return root;
}
int Find( int root, char *s )
{
int i, t;
for( i=0; s[i]; i++ )
{
t = s[i] - 'a';
if( !tree[root].next[t] ) //单词中该字母未出现
return 0;
root = tree[root].next[t];
}
return tree[root].data;
}
int main()
{
int n, m;
char word[11];
while( cin >> n >> m )
{
if( n == 0 && m == 0 ) break;
top = 0;
int root = create_empty();
//建立空树
while( n-- )
{
cin >> word;
Insert( root, word ); //将单词插入树中
}
while( m-- )
{
cin >> word;
if( Find( root, word ))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}