Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18386 Accepted Submission(s): 6192
/* 如果一个电话号码是另一个电话号码的前缀的话,那么就会产生错误 在字典树上加一个v数组表示以i节点为前缀的单词数 如果一个单词在树上是两个单词或以上前缀的话,就说明他除了自己还是别人的前缀就产生错误了 */ #include<bits/stdc++.h> using namespace std; #define MAX 26 #define N 100005 #define M 100 const int maxnode=4000*100+100;///预计字典树最大节点数目 const int sigma_size=10;///每个节点的最多儿子数 struct Trie { ///这里ch用vector<26元素的数组> ch;实现的话,可以做到动态内存 int ch[maxnode][sigma_size];///ch[i][j]==k表示第i个节点的第j个儿子是节点k int val[maxnode];///val[i]==x表示第i个节点的权值为x int sz;///字典树一共有sz个节点,从0到sz-1标号 int v[maxnode]; ///初始化 void Clear() { sz=1; memset(ch[0],0,sizeof(ch[0]));///ch值为0表示没有儿子 memset(v,0,sizeof v); } ///返回字符c应该对应的儿子编号 int idx(char c) { return c-‘0‘; } ///在字典树中插入单词s,但是如果已经存在s单词会重复插入且覆盖权值 ///所以执行Insert前需要判断一下是否已经存在s单词了 void Insert(char *s) { int u=0,n=strlen(s); for(int i=0;i<n;i++) { int id=idx(s[i]); if(ch[u][id]==0)///无该儿子 { ch[u][id]=sz; memset(ch[sz],0,sizeof(ch[sz])); val[sz++]=0; } u=ch[u][id]; v[u]++; } val[u]=n; } ///在字典树中查找单词s int Search(char *s) { int n=strlen(s),u=0; for(int i=0;i<n;i++) { int id=idx(s[i]); if(ch[u][id]==0) return false; u=ch[u][id]; //cout<<"s="<<s<<" v[u]="<<v[u]<<endl; } return v[u]; } }; Trie trie;///定义一个字典树 char op[N][M]; int main() { //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin); int t,n; scanf("%d",&t); while(t--) { trie.Clear(); scanf("%d",&n); getchar(); int f=0; for(int i=0;i<n;i++) { //cout<<i<<endl; scanf("%s",op[i]); //getchar(); //cout<<"=="<<op[i]<<"=="<<endl; trie.Insert(op[i]); } for(int i=0;i<n;i++) { //cout<<"trie.Search(op[i])="<<trie.Search(op[i])<<endl; //cout<<"op[i]="<<op[i]<<endl; if(trie.Search(op[i])>=2) { f=1; break; } } if(f) puts("NO"); else puts("YES"); } return 0; }
原文:http://www.cnblogs.com/wuwangchuxin0924/p/6006112.html