本文共 789 字，大约阅读时间需要 2 分钟。
突破口：
节点属性num[node]：以该单词为前缀的单词数。 当num[node]=1或者字符串扫描结束时，就是该单词的Shortest Profix。代码如下：
#include#include #include #include #include using namespace std;const int maxn=1e4+5;char s[1005][25],ans[1005][25];int Trie[maxn][26];int num[maxn]={0};int tot=1;void insert(char *str){ int len,node,i; len=strlen(str)-1; node=0; for(i=0;i<=len;i++) { if(Trie[node][str[i]-'a']==0) Trie[node][str[i]-'a']=tot++; node=Trie[node][str[i]-'a']; num[node]++; } } void inquire(char *str1,char *str2){ int len,node,i; len=strlen(str1)-1; node=0; for(i=0;i<=len;i++) { if(num[node]==1) //这个要放在最前面。 break; node=Trie[node][str1[i]-'a']; str2[i]=str1[i]; } str2[i]='\0';}int main(){ int i,j; i=j=0; while(cin>>s[i]) { insert(s[i]); i++; } while(j
转载地址：http://vddci.baihongyu.com/