题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=1671
分析：字典树题目变种，这里的字典树指的是0--9的变化。基本原理没有大的变化就是字典树查找。
（1）这道题就是找到这组电话号码中是否有 某个电话号码的前n-1个子串是否由其他的电话号码组成。是就输出NO,否就输出YES.题目大意很简单，字典树时的使用就是套模板，做这种题第一次最好自己写一遍模板，以后自己可以直接使用自己的模板。我的字典树模板见 字典树模板。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define MAXNUM 10 using namespace std; //定义字典树 typedef struct Trie { bool flag;//从根到此是否为一个单词 Trie *next[MAXNUM]; }Trie; Trie *root; void init() { root = (Trie *)malloc(sizeof(Trie)); root->flag=false; for(int i=0;i<MAXNUM;i++) root->next[i]=NULL; } void insert(char *word) { Trie *tem = root; while(*word!='\0') { if(tem->next[*word-'0']==NULL) { Trie *cur = (Trie *)malloc(sizeof(Trie)); for(int i=0;i<MAXNUM;i++) cur->next[i]=NULL; cur->flag=false; tem->next[*word-'0']=cur; } tem = tem->next[*word-'0']; word++; } tem->flag=true; } bool search(char *word) { Trie *tem = root; for(int i=0;word[i]!='\0';i++) { if(tem==NULL||tem->next[word[i]-'0']==NULL) return 0; tem=tem->next[word[i]-'0']; } return tem->flag; } void del(Trie *cur) { for(int i=0;i<MAXNUM;i++) { if(cur->next[i]!=NULL) del(cur->next[i]); } free(cur); } int main() { int t,n; bool flag; char phone_num[10005][20]; char num[20]; scanf("%d",&t); while(t--) { init(); flag = true; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",phone_num[i]); insert(phone_num[i]); } for(int i=0;i<n;i++) { int len = strlen(phone_num[i]); memset(num,'\0',sizeof(num)); for(int j=0;j<len-1;j++) { num[j]=phone_num[i][j]; if(search(num)) { flag = false; break; } } } if(flag)printf("YES\n"); else printf("NO\n"); del(root); } return 0; }
