HDU-1671 Phone List

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1671

题意：给定n个字符串，问是否有字符串是其他字符串的前缀

思路：字典树裸题，我套板子的

代码:

 1 //#include<bits/stdc++.h>
 2 #include<stdio.h>
 3 #include<iostream>
 4 #include<string.h>
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 typedef long long ll;
 8 typedef long double ld;
 9 const int M = int(1e5)*2 + 5;
10 const int mod = 10056;
11 inline int lowbit(int x) {
12     return x & (-x);
13 }
14 
15 char s[M];
16 int trie[M][15],cnt[M];
17 bool f;
18 int tot;
19 void insert(){
20     int root=0;
21     for(int i=0;s[i];i++){
22         int id=s[i]-'0';
23         if(trie[root][id]==0){
24             trie[root][id]=tot++;
25         }
26         root=trie[root][id];   
27     }
28     cnt[root]++;
29 }
30 void search()
31 {
32     int root=0;//从根结点开始找
33     for(int i=0;s[i];i++)
34     {
35         int x=s[i]-'0';//
36         if(trie[root][x]==0)   return;//以root为头结点的x字母不存在，返回0 
37         if(cnt[trie[root][x]]!=0){
38             f=1;
39             return;
40         }
41         root=trie[root][x];//为查询下个字母做准备，往下走 
42     }
43     f=1;//找到了
44 }
45 
46 int main()
47 {
48     int n;cin>>n;
49     while(n--){
50         memset(trie,0,sizeof(trie));
51         memset(cnt,0,sizeof(cnt));
52         tot=1;f=0;
53         int m;cin>>m;
54         for(int i=0;i<m;i++){
55             scanf("%s",s);
56             if(f==1) continue;
57             search();
58             insert();
59         }
60         
61         if(f==0){
62             printf("YES
");
63         }
64         else{
65             printf("NO
");
66         }
67     }
68     return 0;
69 }