JS's Blog
0%

Hdu 1671 -Phone List （字典树模板）

Posted on Edited on In ,

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

题目大意：
给出nn个字符串，询问是否存在某个串完全为另一个串的前缀

分析：
将字符串按长度排序后插入即可，当前字符串插入字典树时，若中途发现该结点为单词，说明该单词的前缀已被插入，返回falsefalse，若全部能顺利插入则返回truetrue

注意：如果使用指针构造字典树，交G可能会爆空间，建议交C

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long ll;


struct Trie{
    Trie *next[10];
    int val;
    Trie(){
        val = 0;
        for (int i = 0 ; i < 10 ; i ++)
            next[i] = NULL;
    }
};

bool addword(char *str,Trie* node)
{

    if (node->val!=0)
        return false;
    if (node->next[str[0]-'0']==NULL)
        node->next[str[0]-'0'] = new Trie;
    node = node->next[str[0]-'0'];
    str++;
    //printf("%d\t",*str);
    if (*str)
        return addword(str,node);
    else
    {
        node->val++;
        return true;
    }
}

int query(char *str ,Trie *node)
{
   // printf("%d\t",*str);
    if (node->next[*str-'0']==NULL)
        return 0;
    else
        node= node->next[*str-'0'];
    ++str;
    if (*str)
        return query(str,node);
    else
        return node->val;
}

void del(Trie *node)
{
    for (int i = 0 ; i < 10 ; i ++)
    {
        if (node->next[i]!=NULL)
            del(node->next[i]);
    }
    delete node;
    node = NULL;
    return;
}
struct String{
    char str[20];
    int len;
    void read()
    {
        scanf("%s",str);
        len = strlen(str);
    }
    bool operator <(const String& a)
    {
        return len<a.len;
    }
}s[12000];


int main()
{
    int T,n;
    //printf("hello\n");
    Trie *head;
    //printf("world\n");
    scanf("%d",&T);

    while (T--)
    {

        scanf("%d",&n);
        head = new Trie;
        for (int i = 1;  i <= n ; i ++)
        {
            s[i].read();
        }
        sort(s+1,s+n+1);
        int f = 1;
        //printf("ok\n");
        for (int i = 1 ; i <= n ; i ++)
        {
            if (!addword(s[i].str,head))
            {
                f = 0;
                break;
            }
        }
        //printf("fuck\n");
        if (!f)
            printf("NO\n");
        else
            printf("YES\n");
        del(head);

    }

    return 0;
}