Categories

hdu 1247 hatword(第一次写trie)

第一次写trie,orz smallwood师兄写的模板.

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
#include <iostream>
#include <string>
#define msize 50005
#define SIZE 26
#define MAXN 102400
using namespace std;
 
class Trie
{
public:
    struct node
    {
        int words;
        int prefixes;
        int edges[SIZE]; //支持26个小写英文字母
    };
    node Tree[MAXN];
    int N;
 
    void initTrie(void)
    {
        init(0);
        N = 1;
    }
    void init(int i)
    {
        Tree[i].words = 0;
        Tree[i].prefixes = 0;
        for (int j = 0; j < SIZE; j++) Tree[i].edges[j] = -1;
    }
    void addWord(int i, char* word)
    {
        if (word[0] == ‘\0) Tree[i].words++;
        else
        {
            Tree[i].prefixes++;
            int k = word[0] – ‘a’;
            if (Tree[i].edges[k] == -1)
            {
                Tree[i].edges[k] = N++;
                init(Tree[i].edges[k]);
            }
            addWord(Tree[i].edges[k], word + 1);
        }
    }
    int countWords(int i, char* word)
    {
        int k = word[0] – ‘a’;
        if (word[0] == ‘\0) return Tree[i].words;
        else if (Tree[i].edges[k] == -1) return 0;
        else return countWords(Tree[i].edges[k], word + 1);
    }
    int countPrefixes(int i, char* prefix)
    {
        int k = prefix[0] – ‘a’;
        if (prefix[0] == ‘\0) return Tree[i].prefixes;
        else if (Tree[i].edges[k] == -1) return 0;
        else return countPrefixes(Tree[i].edges[k], prefix + 1);
    }
};
 
char dic[msize][16];
Trie T;
 
int main()
{
    int n=6;
    T.initTrie();
    while (scanf(%s”,dic[n])==1) T.addWord(0,dic[n]),n++;
//    for(int i=0;i<6;i++)
//    {
//         scanf(”%s”,dic[i]);
// T.addWord(0,dic[i]);
//    }
 
    for (int i=0;i<n;i++)
    {
        int m=strlen(dic[i]);
        for (int j=1;j<=m-1;j++)
        {
            char ch=dic[i][j];
            dic[i][j]=0;
            if (T.countWords(0,dic[i])==1)
            {
                dic[i][j]=ch;
                if (T.countWords(0,&dic[i][j])==1)
                {
                    printf(%s\n“,dic[i]);
                    break;
                }
            }
            dic[i][j]=ch;
        }
    }
 
    return 0;
}

2 comments to hdu 1247 hatword(第一次写trie)

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*