题目链接：

http://poj.org/problem?id=2001

http://bailian.openjudge.cn/practice/2001

总时间限制: 1000ms 内存限制: 65536kB

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", "car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate" is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo".

An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car" , not for "carriage" or any of the other words in the list that begins with "car".
Input
The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.
Output
The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

题意：

给出若干个由小写字母组成的单词，要你找出每个单词的最短的前缀子串，要求该前缀子串是唯一的，不在其他任何单词内出现。

但是，精确匹配优先级高于前缀匹配，也就是说，即使 "car" 整个单词都是其他单词的前缀，但是 "car" 依然唯一代表单词 "car"。

题解：

对字典树上的每一个节点，新增一个 $pre$ 用以标记该节点对应的一个子串是多少个单词的前缀。

每次查询，沿着字典树不断往下枚举，不断加长前缀，直到发现 $pre=1$ 就跳出。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int tot;
string str[maxn];

namespace Trie
{
    const int SIZE=maxn*20;
    int sz;
    struct TrieNode{
        int pre;
        bool ed;
        int nxt[26];
    }trie[SIZE];
    void init()
    {
        sz=1;
        memset(trie,0,sizeof(trie));
    }
    void insert(const string& s)
    {
        int p=1;
        for(int i=0;i<s.size();i++)
        {
            int ch=s[i]-'a';
            if(!trie[p].nxt[ch]) trie[p].nxt[ch]=++sz;
            p=trie[p].nxt[ch];
            trie[p].pre++;
        }
        trie[p].ed=1;
    }
    bool search(const string& s)
    {
        int p=1;
        for(int i=0;i<s.size();i++)
        {
            p=trie[p].nxt[s[i]-'a'];
            if(!p) return 0;
        }
        return trie[p].ed;
    }
    string prefix(const string& s)
    {
        string res;
        int p=1;
        for(int i=0;i<s.size();i++)
        {
            p=trie[p].nxt[s[i]-'a'];
            res+=s[i];
            if(trie[p].pre<=1) break;
        }
        return res;
    }
};

int main()
{
    tot=0;
    Trie::init();
    while(cin>>str[++tot])
    {
        if(!Trie::search(str[tot])) {
            Trie::insert(str[tot]);
        }
    }
    for(int i=1;i<=tot;i++)
    {
        cout<<str[i]<<" "<<Trie::prefix(str[i])<<endl;
    }
}

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

微信扫一扫
关注该公众号