HDU 1251 字典树 前缀计数

本文主要是介绍HDU 1251 字典树 前缀计数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

加入单词时 路径上每个点得count值都加一
查询直接输出 单词节点的count值

#include <cstdio>
#include <cstring>
#define sf scanf
#define pf printf
using namespace std;
struct Trie_node{int count;struct Trie_node* next[26];
}Root;typedef Trie_node* P_node;int idx(char x){return x - 'a';
}void Insert(char* s){int len = strlen(s);P_node cur = &Root;for(int i = 0;i < len;++i){P_node& next = cur -> next[idx(s[i])];if(next == NULL){next = new Trie_node;next -> count = 0;for(int i = 0;i < 26;++i) next -> next[i] = NULL;}cur = next;cur -> count++;}
}int Search(char *s){int len = strlen(s);P_node cur = &Root;for(int i = 0;i < len;++i){cur = cur -> next[idx(s[i])];if(cur == NULL) return 0;}return cur -> count;
}int main(){char s[15];while( gets(s) && strlen(s) ){Insert(s);}while( gets(s) != 0 && strlen(s) ){pf("%d\n",Search(s));}return 0;
}

这篇关于HDU 1251 字典树 前缀计数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---