hdu1671 字典树记录前缀出现次数
题意:
给你一堆电话号,问你这些电话号后面有没有相互冲突的,冲突的条件是当前这个电话号是另一个电话号的前缀,比如有 123456789 123,那么这两个电话号就冲突了,直接输出NO。
思路:
给你一堆电话号,问你这些电话号后面有没有相互冲突的,冲突的条件是当前这个电话号是另一个电话号的前缀,比如有 123456789 123,那么这两个电话号就冲突了,直接输出NO。
思路:
说白了就是前缀匹配,也就是以当前字符串为前缀的字符串有几个,只要有一个或者更多那么就直接NO了,快速的判断前缀的问题我们可以直接字典树记录前缀,先把所有的字符串都存在字典里,然后在枚举每一个,只要有一个是前缀(不算自己)那么就直接NO了,这里要注意一点,每次都要把Tree的内存清空,不然不同的mallco不释放,测试数据多了就MLE了。
#include<stdio.h> #include<string.h> #include<stdlib.h> char str[10005][12]; typedef struct Tree { Tree *next[10]; int v; }Tree; Tree root; void Buid_Tree(char *str) { int len = strlen(str); Tree *p = &root ,*q; for(int i = 0 ;i < len ;i ++) { int id = str[i] - '0'; if(p -> next[id] == NULL) { q = (Tree *) malloc(sizeof(root)); q -> v = 1; for(int j = 0 ;j < 10 ;j ++) q -> next[j] = NULL; p -> next[id] = q; p = p -> next[id]; } else { p = p -> next[id]; p -> v ++; } } } int Find(char *str) { int len = strlen(str); Tree *p = &root; for(int i = 0 ;i < len ;i ++) { int id = str[i] - '0'; p = p -> next[id]; if(p == NULL) return 0; } return p -> v; } bool solve(int n) { for(int i = 1 ;i <= n ;i ++) if(Find(str[i]) != 1) return 0; return 1; } int dealTree(Tree* T) { int i; if(T==NULL) return 0; for(i=0;i<10;i++) { if(T->next[i]!=NULL) dealTree(T->next[i]); } free(T); return 0; } int main () { int t ,n ,i; scanf("%d" ,&t); while(t--) { scanf("%d" ,&n); for(i = 0 ;i < 10 ;i ++) root.next[i] = NULL; for(i = 1 ;i <= n ;i ++) { scanf("%s" ,str[i]); Buid_Tree(str[i]); } if(solve(n)) puts("YES"); else puts("NO"); dealTree(&root); } return 0; }