首页 > 代码库 > poj 3630 Phone List(字典树)
poj 3630 Phone List(字典树)
题目链接: http://poj.org/problem?id=3630
思路分析:
求在字符串中是否存在某个字符串为另一字符串的前缀:
即对于某个字符串而言，其是否为某个字符串的前缀,或存在某个其先前的字符串为其前缀；
(1)若该字符串为某个字符串前缀，则存在一条从根节点到该字符串的最后一个字符串的路径;
(2)若存在某个字符串为该字符串前缀，则在该字符串的查找路径中存在一条子路径，路径的最后的结点的endOfWord
标记为true，表示存在某个字符串为其前缀；
代码：
#include <iostream>using namespace std;const int MAX_N = 10;struct Trie{ bool endOfWord; Trie *next[MAX_N]; Trie() { for (int i = 0; i < MAX_N; ++i) next[i] = NULL; endOfWord = false; }};int nodeCount = 0;Trie *root = NULL;Trie memory[600000];bool insertAndJudge(char *word){ Trie *cur = root, *next; int len = strlen(word); for (int i = 0; i < len; ++ i) { int k = word[i] - ‘0‘; if (cur->next[k] == NULL) { next = &memory[nodeCount++]; cur->next[k] = next; cur = cur->next[k]; } else if (i == len - 1 || cur->next[k]->endOfWord == true) return false; else cur = cur->next[k]; } cur->endOfWord = true; return true;}int main(){ int t; cin >> t; while (t--) { int n; bool flag = true; char word[15]; nodeCount = 0; memset(memory, 0, sizeof(memory)); root = &memory[nodeCount++]; cin >> n; while (n--) { scanf("%s", word); if (flag) flag = insertAndJudge(word); } if (flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0;}
poj 3630 Phone List(字典树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。