【DescriptionDescription】We know that if a phone number A is another phone number B’s prefix, B is not able tobe called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and notable to call B.Given N phone numbers, your task is to find whether there exits two numbers A and Bthat A is B’s prefix.Input【InputInput】The input consists of several test cases.The first line of input in each test case contains one integer N (0<N<1001), represent thenumber of phone numbers.The next line contains N integers, describing the phone numbers.The last case is followed by a line containing one zero.Output【OutputOutput】For each test case, if there exits a phone number that cannot be called, print “NO”,otherwise print “YES” instead.Sample Input】【Sample Input20120123452120123450Sample Output】【Sample OutputNOYES
1 #include<stdio.h> 2 #include<stdlib.h> 3 struct node 4 { 5 int flag; 6 struct node *next[10]; 7 }*root; 8 int tag; 9 struct node *creat() 10 { 11 struct node *p; 12 p=(struct node *)malloc(sizeof(struct node)); 13 p->flag=0; 14 for(int i=0;i<10;i++) 15 p->next[i]=NULL; 16 return p; 17 } 18 void inser(char *s) 19 { 20 int i; 21 struct node *p; 22 p=root; 23 for(i=0;s[i]!='\0';i++) 24 { 25 if(!(p->next[s[i]-'0'])) p->next[s[i]-'0']=creat(); 26 p=p->next[s[i]-'0']; 27 if(p->flag==1) tag=1;判断p节点是否是某字符串的结束。 28 } 29 p->flag=1; 30 } 31 int main () 32 { 33 int t; 34 char s[1010]; 35 while(~scanf("%d",&t)) 36 { 37 if(!t) break; 38 root=creat(); 39 tag=0; 40 while(t--) 41 { 42 scanf("%s",s); 43 inser(s); 44 } 45 if(tag==1) 46 printf("NO\n"); 47 else printf("YES\n"); 48 } 49 return 0; 50 }
转载于:https://www.cnblogs.com/LK1994/archive/2013/04/13/3019029.html
