STEP BY STEP

POJ百练 - 2797:最短前缀(可以使用字典树做)

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

链接: http://poj.grids.cn/practice/2797/

这题乍看之下确实没什么思路,后面终于明白题意了,然后突然想到可以用字典树做,速度当然会是非常快的…
但是其实还有一种更简单的方法,那就是对所有字符串排序之后,每个字符串的前缀长度其实就是由其前一个和后一个字符串共同决定,
nLen = max(nOne, nTwo), nOne 和 nTwo就分别代表当前字符串和前后字符串公告部分的长度+1后的值…
代码写出来写非常简单…同学这样实现了下,也轻松过了…

然后我就辛苦的写了一棵字典树…可能我的写法不是很标准,因为我没参考什么模板,自己硬想出来怎么写的…
我的想法是开一个静态大数组,第一个结点作为根,不存储数据,从第二个结点开始作为自由空间分配…
其实,就是对26颗字典树虚拟了个无数据的根结点…
使用了虚拟的根结点后,代码比用26个根结点简洁很多…
刚开始我就假设1-26号结点分别为a-z,作为26颗树的根,
而且下26个结点的位置我用的是索引,没用指针,后面换成了指针,代码看起来更舒服了…

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
#include <stdio.h>
#include <string.h>
#define LETTER_NUM 26
#define WORD_LEN_MAX 25
#define WORD_NUM_MAX 1030
#define NODE_MAX (WORD_LEN_MAX * WORD_NUM_MAX + 10)
struct WORD_TREE
{
    char ch;
    WORD_TREE* next[LETTER_NUM];
    int nTime;
};
WORD_TREE tree[NODE_MAX];
WORD_TREE* pFreeNode = tree + 1;//第一个结点作为头结点,不存储数据
char szWords[WORD_NUM_MAX][WORD_LEN_MAX];
void AddToTree(char* pszStr)
{
    WORD_TREE* pTree = tree;
    while (*pszStr && pTree->next[*pszStr - 'a'])
    {
        pTree = pTree->next[*pszStr - 'a'];
        pTree->nTime++;
        ++pszStr;
    }
    while (*pszStr)
    {
        pFreeNode->ch = *pszStr;
        pFreeNode->nTime++;
        pTree->next[*pszStr - 'a'] = pFreeNode;
        pTree = pFreeNode;
        ++pszStr;
        ++pFreeNode;
    }
}
int FindPrefix(char* pszStr)
{
    WORD_TREE* pTree = tree;
    int nLen = 0;
    while (*pszStr)
    {
        ++nLen;
        pTree = pTree->next[*pszStr - 'a'];
        if (pTree->nTime <= 1)
        {
            break;
        }
        ++pszStr;
    }
    return nLen;
}
int main()
{
    int nCount = 0;
    while (scanf("%s", szWords[nCount]) != EOF)
    {
        AddToTree(szWords[nCount]);
        nCount++;
    }
    for (int i = 0; i < nCount; ++i)
    {
        int nLen = FindPrefix(szWords[i]);
        printf("%s ", szWords[i]);
        for (int j = 0; j < nLen; ++j)
        {
            putchar(szWords[i][j]);
        }
        putchar('\n');
    }
    return 0;
}
相关文章