【POJ2001】Shortest Prefixes

本文主要是介绍【POJ2001】Shortest Prefixes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=2001
题意：给出若干字符串，求每一个字符串的最短唯一表示前缀
题解：
一看这种找前缀的东西肯定是trie
插入的时候每路过一个点，cnt++
查询的时候走到第一个cnt=1即可，如果没有，就输出这个串

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[1010][25];
int nxt[25010][26],cnt[25010];
int n,num=1;void insert(char *s)
{int len=strlen(s+1),t=1;for(int i=1;i<=len;i++){if(nxt[t][s[i]-'a']==0) nxt[t][s[i]-'a']=++num;cnt[nxt[t][s[i]-'a']]++;t=nxt[t][s[i]-'a'];}
}void search(int k,char *s)
{int len=strlen(s+1),t=1;for(int i=1;i<=len;i++){if(cnt[nxt[t][s[i]-'a']]==1){for(int j=1;j<=i;j++) printf("%c",str[k][j]);printf("\n");return;}t=nxt[t][s[i]-'a'];}printf("%s\n",str[k]+1);return;
}int main()
{
//  freopen("in.in","r",stdin);
//  freopen("out.out","w",stdout);while(~scanf("%s",str[++n]+1)) insert(str[n]);for(int i=1;i<=n;i++){printf("%s ",str[i]+1);search(i,str[i]);   }return 0;
}

这篇关于【POJ2001】Shortest Prefixes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---