题意:
给定多个单词组成的词典, 输出每个单词对应的前缀, 使得每个前缀唯一.
如果不存在就输出单词本身. 也就是:找出一个前缀,该前缀能唯一表示该字符串.
分析:
建立Trie树,每个节点的V代表有多少个字符串路径上含有它.
Find函数里查找每个单词的前缀,知道v值==1返回即可.
#include<cstdio>
#include<iostream>
#include<cstring>using namespace std;const int maxn = 1e7+11;struct node
{int ch[maxn][26];int v[maxn];int sz;void init(){sz=1;memset(ch[0],0,sizeof ch[0]);v[0]=0;}void insert(char *s){int n=strlen(s),u=0;for(int i=0;i<n;i++){int id=s[i]-'a';if(!ch[u][id]){ch[u][id]=sz;memset(ch[sz],0,sizeof ch[sz]);v[sz]=0;sz++;}u=ch[u][id];v[u]++;}}void find(char *s){int n=strlen(s),u=0;for(int i=0;i<n;i++){int id=s[i]-'a';u=ch[u][id];printf("%c",s[i]);if(v[u]==1)//该字符已经能唯一标示该单词return;}}
}trie;int main()
{char word[1111][33];trie.init();int cnt=0;while(scanf("%s",word[cnt])==1){trie.insert(word[cnt++]);}for(int i=0;i<cnt;i++){printf("%s ",word[i]);trie.find(word[i]);puts("");}
}