首页 > 代码库 > POJ 3630 Trie
POJ 3630 Trie
链接：
http://poj.org/problem?id=3630
题意：
给你n个字符串，判断有没有字符串是其他字符串的前缀
题解：
建一个字典树，在插入的过程中，如果没有新建一个结点，那这个字符串肯定是其他字符串的前缀，
如果新建结点的时候发现，有的字符串以这个字符结尾，那肯定有字符串是这个字符串的前缀
代码：
31 int pi = 1;32 int fg;33 34 struct Node {35 int next[10];36 bool end;37 }tree[MAXN];38 39 void insert(string keyword) {40 int index, p, i;41 int flag = 0;42 for (i = p = 0; keyword[i]; i++) {43 index = keyword[i] - ‘0‘;44 if (tree[p].next[index] == 0) {45 tree[p].next[index] = pi++;46 flag = 1;47 if (tree[p].end) fg = 0;48 }49 p = tree[p].next[index];50 }51 if (!flag) fg = 0;52 tree[p].end = 1;53 }54 55 int main() {56 int T;57 cin >> T;58 while (T--) {59 pi = 1;60 fg = 1;61 memset(tree, 0, sizeof(tree));62 int n;63 cin >> n;64 while (n--) {65 string s;66 cin >> s;67 insert(s);68 }69 if (fg) cout << "YES" << endl;70 else cout << "NO" << endl;71 }72 return 0;73 }
POJ 3630 Trie
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。