<题目链接>
题目大意：
找出能唯一标示一个字符串的最短前缀，如果找不出，就输出该字符串。
解题分析：
Trie树的简单应用，对于每个单词的插入，都在相应字符对应的节点 num 值+1 ，这样在查询的时候，如果遍历到num值为1的节点，就可以确定，该前缀能够唯一确定一个字符串，或者是一直遍历到NULL,这时直接输出它本身即可。
指针式Trie树：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N =1e3+;
char word[N][];
struct Node{
int num;
Node *next[];
Node(){
num=;
for(int i=;i<;i++)
next[i]=NULL;
}
};
Node *root;
Node *now,*newnode;
void Insert(char *str){
now=root;
for(int i=;i<strlen(str);i++){
int to=str[i]-'a';
if(now->next[to]==NULL){ //如果该节点为空
newnode=new Node;
++(newnode->num);
now->next[to]=newnode;
now=now->next[to];
}
else{
now=now->next[to];
++(now->num);
}
}
}
void Search(char *str){
char ans[];
now=root;
for(int i=;i<strlen(str);i++){
int to=str[i]-'a';
now=now->next[to];
ans[i]=str[i]; //ans[]记录下前缀字符串
ans[i+]='\0';
if(now->num==){ //如果该节点只有一个对应的公共前缀，那么就是它本身的前缀，所以直接输出该节点的对应前缀即可
printf("%s %s\n",str,ans);
return;
}
}
printf("%s %s\n",str,str);
}
int main(){
root=new Node;
int cnt=;
while(gets(word[++cnt])){
//if(!strlen(word[cnt]))break;
Insert(word[cnt]);
}
for(int i=;i<=cnt;i++)Search(word[i]);
return ;
}
数组式Trie树 转载于 >>>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char a[][];
int tot,size;
int sz,t[][],s[];
void insert(char ch[])
{
int k,len=strlen(ch+),now=;
for(int p=;p<=len;p++)
{
k=ch[p]-'a';
if(t[now][k]==)t[now][k]=++sz;
now=t[now][k];
s[now]++;
}
}
void ask(char ch[])
{
int now=,k,len=strlen(ch+);
for(int p=;p<=len;p++)
{
if(s[now]==)break;
k=ch[p]-'a';
printf("%c",ch[p]);
now=t[now][k];
}
}
int main()
{
while(scanf("%s",a[++tot]+)!=EOF)insert(a[tot]);
for(int i=;i<=tot;i++)
{
printf("%s ",a[i]+);
ask(a[i]);
printf("\n");
}
return ;
}
2018-10-29