题解:这题可算是Trie树 模板题。在hdu 1251 的discuss里有一个用数组模拟的 速度貌似很快。但这题建议用来练Trie树。自己先写出代码来,然后再对比别人的模板,看你的思路哪里有错,错的地方就是重点。日后拓展时用到Trie树 就会顺手拈来,改哪里动哪里你都知道会产生什么样的情况,那样你就能将Trie树很好的融合进你的解题思路里去,以期达到快速切题。
题意就一组测试数据,空行前是单词数,空行后是要查的前缀,输出有这样的前缀的单词的个数,对于空行的读取 采用gets()函数就行了,只要s[0]==0就是空行。
代码有点水,没有释放内存,要释放的话貌似时间上会变长很多。。
我的释放代码:
void release(TrieNode *p){ int i; for(i = 0; i < MAX; i++){ if(p->next[i] != NULL){ release(p->next[i]); } } delete p; return ; }
调用 release(root) 就可以了。
不知还有其它可行的方法没,诚求。
hdu 1251
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define MAX 26 typedef struct Node{ int isStr; int num; struct Node *next[MAX]; }TrieNode,*Trie; Trie root; void create(){ root = new TrieNode; memset(root->next,NULL,sizeof(root->next)); root -> isStr = 0; root -> num = 0; } void Insert(char *s){ int i; TrieNode *p = root,*q; while(*s){ if(p ->next[*s-'a'] == NULL){ q = new TrieNode; memset(q->next,NULL,sizeof(q->next)); q->num = 1; q->isStr = 0; p ->next[*s-'a'] = q; } else { p ->next[*s-'a'] -> num ++; } p = p ->next[*s-'a']; s++; } p->isStr = 1; } int find(char *s){ int i; TrieNode *p=root,*q; while(*s){ if(p->next[*s-'a'] == NULL)return 0; p = p->next[*s-'a']; s++; } return p->num; } int main() { char s[MAX]; create(); while(gets(s)){ if(s[0] == 0){ break; } Insert(s); } while(cin>>s){ cout << find(s) <<endl; } }