题目链接：http://poj.org/problem?id=3630 这道题和1056是一样的，都是判断一个单词是否是另一个单词的前缀
  view code
1 #include <cstdio>
2 #include <cstring>
3 struct trie{
4 int ch[100100][12];
5 int val[100100];
6 int sz;
7 void reset(){
8 memset(ch[0], 0, sizeof(ch[0]));
9 memset(val, 0, sizeof(val));
10 sz = 1;
11 }
12 int idx(char c){
13 return c - '0';
14 }
15 void insert(char *s, int v){
16 int u = 0, n = strlen(s);
17 for (int i = 0; i < n; i++){
18 int c = idx(s[i]);
19 if (!ch[u][c]){
20 memset(ch[sz], 0, sizeof(ch[sz]));
21 ch[u][c] = sz;
22 val[sz] = 0;
23 sz += 1;
24 }
25 u = ch[u][c];
26 }
27 val[u] = v;
28 }
29 bool query(char *s, int v){
30 int u = 0, n = strlen(s), cnt = 0;
31 for (int i = 0; i < n; i++){
32 int c = idx(s[i]);
33 u = ch[u][c];
34 if (val[u] == v) cnt += 1;
35 }
36 if (cnt > 1) return 0;
37 return 1;
38 }
39 }t;
40 char s[10010][12];
41 int main(){
42 int p, n;
43 scanf("%d", &p);
44 while (p--){
45 t.reset();
46 scanf("%d", &n);
47 for (int i = 0; i < n; i++){
48 scanf("%s", s[i]);
49 t.insert(s[i], -1);
50 }
51 bool f = 1;
52 for (int i = 0; i < n; i++)
53 if (!t.query(s[i], -1)){
54 f = 0; break;
55 }
56 if (!f) printf("NO\n");
57 else printf("YES\n");
58 }
59 return 0;
60 }
61
|