问题理解

我们需要为给定的单词列表中的每个单词找到一个最短的前缀，该前缀能够唯一标识该单词。也就是说，这个前缀在单词列表中只出现一次，不会与其他单词的前缀冲突。如果单词本身是唯一的（即没有其他单词以它开头），那么该单词的最短唯一前缀就是它自己。

解决思路

数据结构选择：使用Trie（前缀树）数据结构来高效地存储和查询单词的前缀。Trie可以帮助我们快速查找某个前缀是否唯一。 构建Trie： 每个节点表示一个字符，从根节点到某个节点的路径表示一个前缀。 每个节点维护一个计数器cnt，表示有多少单词经过该节点。 插入单词： 对于每个单词，逐个字符插入到Trie中，并在每个经过的节点上增加计数器。 查找最短唯一前缀： 对于每个单词，从根节点开始，逐个字符遍历。 在每个节点检查计数器cnt，如果cnt为1，说明当前前缀是唯一的，可以停止遍历。

代码实现

以下是基于上述思路的C++代码实现：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair<int,int>
#define maxn 20005
#define inf 1000000000
using namespace std;
 
struct trie_type {
    int cnt, next[30];
} t[maxn];
 
int tot = 0, n = 0;
char s[1005][25];
 
inline void insert(char *ch) {
    int p = 0, l = strlen(ch);
    F(i, 0, l - 1) {
        int tmp = ch[i] - 'a';
        if (!t[p].next[tmp]) t[p].next[tmp] = ++tot;
        p = t[p].next[tmp];
        t[p].cnt++;
    }
}
 
inline void find(char *ch) {
    int p = 0, l = strlen(ch);
    printf("%s ", ch);
    F(i, 0, l - 1) {
        printf("%c", ch[i]);
        int tmp = ch[i] - 'a';
        p = t[p].next[tmp];
        if (t[p].cnt == 1) break;
    }
    printf("\n");
}
 
int main() {
    while (~scanf("%s", s[++n])) insert(s[n]);
    F(i, 1, n - 1) find(s[i]);
    return 0;
}

代码解释

Trie结构定义： trie_type结构体表示Trie的节点，包含一个计数器cnt和一个长度为26的数组next，用于存储子节点的索引。 插入函数insert： 遍历单词的每个字符，将字符转换为索引（tmp = ch[i] - 'a'）。 如果当前字符对应的子节点不存在，则创建一个新节点。 移动到子节点，并增加该节点的计数器cnt。 查找函数find： 遍历单词的每个字符，逐个输出字符。 在每个节点检查计数器cnt，如果cnt为1，说明当前前缀是唯一的，停止遍历。 主函数main： 读取输入单词，调用insert函数将每个单词插入到Trie中。 调用find函数为每个单词查找最短唯一前缀，并输出结果。