程序员人生 网站导航

hihoCoder 1107 Shortest Proper Prefix (字典树的遍历)

栏目:php教程时间:2015-05-06 08:33:09

题目链接:

http://hihocoder.com/problemset/problem/1107?sid=406355


题意:

求频率不超过5的前缀的数目。字典树的遍历


代码以下:

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10010; const int max_size = 30; int id(char c){ return c-'a'; } struct Trie{ Trie *ch[max_size]; int num; Trie(){ num = 0; for(int i=0;i<max_size;i++) ch[i]=NULL; } }*root; void insert_str(char *s){ Trie *p = root; p->num++; for(int i=0; p&&s[i] ; i++){ int u = id(s[i]); if(p->ch[u]==NULL) p->ch[u] = new Trie; p=p->ch[u]; p->num++; } } int find_str(char *s){ Trie *p = root; for(int i=0;p&&s[i];i++){ int u = id(s[i]); if(p->ch[u]==NULL) return 0; p=p->ch[u]; } return p->num; } int ans; void vis(Trie *nod){ Trie *p=nod; if(p->num<=5&&p->num>0) {ans++;return;} for(int i=0;i<max_size;i++) if(p->ch[i]) vis(p->ch[i]); } char s[2000010]; int main() { int n, m; while(~scanf("%d", &n)){ root = new Trie; for(int i=0;i<n;i++){ scanf("%s", s); insert_str(s); } ans = 0; vis(root); printf("%d ",ans); } return 0; }

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐