首页 > 代码库 > POJ - 3630 代码
POJ - 3630 代码
Trie的简单应用,只涉及插入字符串的操作。
需要注意的是,输入数据有T组,在处理每一组数据之前都要初始化root,由于忽视了这一点WA了n次。
还有一点就是,在发现一组数据答案为“NO”之后,仍然要读完这组数据的字符串。在这一点上也WA了好多次= =
另外,本题大概需要建立4000000个节点,如果采用动态空间建点会TLE。
看来malloc操作确实是很慢啊。
所以提前开一个大的数组空间,静态的就好了。
代码如下:
/*Author : Magician Van*/#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>using namespace std;const int MaxNext = 10 + 2, MaxL = 10 + 2, MaxNode = 100000 + 5;int T, n, top;char Str[MaxL];bool Wrong = false;typedef struct TrieNode { bool isStr; TrieNode *Next[MaxNext];} Trie;Trie Ta[MaxNode];void Insert(Trie *root, char *S, int len){ if (root == NULL || len == 0) return; Trie *p = root; int sum = 0; for (int i = 0; i <= len - 1; i++) { if (p -> Next[S[i] - ‘0‘] == NULL) { Trie *temp = &Ta[++top]; temp -> isStr = false; for (int j = 0; j <= 9; j++) temp -> Next[j] = NULL; p -> Next[S[i] - ‘0‘] = temp; } else sum++; p = p -> Next[S[i] - ‘0‘]; if (p -> isStr) { Wrong = true; return; } } p -> isStr = true; if (sum == len) Wrong = true;} int main(){ scanf("%d", &T); for (int t = 1; t <= T; t++) { top = 0; Trie *root = &Ta[++top]; for (int i = 0; i <= 9; i++) root -> Next[i] = NULL; root -> isStr = false; Wrong = false; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%s", Str); if (!Wrong) Insert(root, Str, strlen(Str)); } if (Wrong) printf("NO\n"); else printf("YES\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。