2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
NO YES
题意：判断给定号码中是否存在某个号码是其他某号码的前缀，存在输出“NO”，否则输出“YES”。
解析：利用字典树处理。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1671
代码清单：
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX = 11;
struct trie{
int point;
trie *next[MAX];
};
trie *root;
int t,n,flag;
char s[MAX];
void Trie(char *s){
trie *p=root, *q;
int len=strlen(s), pos;
for(int i=0;i<len;i++){
pos=s[i]-'0';
if(p->next[pos]==NULL){
q=new trie;
q->point=0;
for(int j=0;j<MAX;j++)
q->next[j]=NULL;
p->next[pos]=q;
p=p->next[pos];
}
else{
if(p->next[pos]->point){ //前面某个号码是当前的前缀
flag=1;
return ;
}
p=p->next[pos];
}
}
p->point=1;
for(int i=0;i<MAX;i++){
if(p->next[i]){ //当前号码是前面某个号码的前缀
flag=1;
return ;
}
}
}
void delTrie(trie *Root){ //释放内存空间
for(int i=0;i<MAX;i++){
if(Root->next[i]!=NULL)
delTrie(Root->next[i]);
}
free(Root);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
root=new trie;
for(int i=0;i<MAX;i++)
root->next[i]=NULL;
flag=0;
for(int i=0;i<n;i++){
scanf("%s",s);
Trie(s);
}
if(flag) printf("NO\n");
else printf("YES\n");
delTrie(root);
}
return 0;
}
原文：http://blog.csdn.net/jhgkjhg_ugtdk77/article/details/44609447