poj 2001 Shortest Prefixes(字典树)

题目链接:http://poj.org/problem?id=2001

思路分析：

在Trie结点中添加数据域childNum，表示以该字符串为前缀的字符数目；

在创建结点时,路径上的所有除叶子节点以外的结点的childNum增加1,叶子结点的childNum设置为1；

在查询某个结点的最短前缀时：

(1)若查找路径上的所有结点的childNum大于1,表明该字符串的最短路径为其自身;

(2)若查找路径上存在结点的childNum等于1,表明查找的字符串是唯一以该字符串为前缀的字符串;

代码如下：

#include <iostream>

#include <cstdlib>

const int MAXN = ;

const int N =  + ;

const int M =  + ;

char dic[N][M];

struct Trie

{

    int childNum;

    Trie *child[MAXN];

    Trie()

    {

        for (int i = ; i < MAXN; ++ i)

            child[i] = NULL;

        childNum = ;

    }

};

Trie *root = NULL;

void insert(char *word)

{

    Trie *cur = root;

    int len = strlen(word);

    for (int i = ; i < len; ++ i)

    {

        int id = word[i] - 'a';

        if (cur->child[id] == NULL)

            cur->child[id] = new Trie;

        else

            cur->child[id]->childNum++;

        cur = cur->child[id];

    }

}

int findShortestPrefixes(char *word)

{

    int i, len = strlen(word);

    Trie *cur = root;

    for (i = ; i < len; ++ i)

    {

        int id = word[i] - 'a';

        cur = cur->child[id];

        if (cur->childNum <= )

            return i;

    }

    return -;

}

int main()

{

    int count = ;

    root = new Trie;

    while (scanf("%s", dic[count]) != EOF)

        insert(dic[count++]);

    for (int j = ; j < count; ++ j)

    {

        int ans = findShortestPrefixes(dic[j]);

        if (ans == -)

            printf("%s %s\n", dic[j], dic[j]);

        else

        {

            printf("%s ", dic[j]);

            dic[j][ans + ] = '\0';

            printf("%s\n", dic[j]);

        }

    }

    return ;

}