程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj2001 Shortest Prefixes

poj2001 Shortest Prefixes

編輯:關於C++

題意:給你一些字符串 對於每個字符串 求出它們特有的最小前綴 輸出格式 字符串 + 最小前綴

思路:字典樹;

代碼:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 1000000000000
#define N 1010
#define LL long long
#define eps 10E-9
#define mem(a) memset(a,0,sizeof(a))
#define w(a) while(a)
#define s(a) scanf("%d",&a)
#define ss(a,b) scanf("%d%d",&a,&b)
#define sss(a,b,c) scanf("%d%d%d",&a,&b,&c)
using namespace std;
char str[N][25];
struct node
{
int sum;
struct node *next[26];
node ()//構造函數 初始化用
{
sum=0;
mem(next);
}
} ;
node *root=NULL;
void maketree(char *s)
{
node *p=root;
node *tmp=NULL;
for(int i=0; i {
if(p->next[s[i]-'a']==NULL)
{
tmp=new node ;
p->next[s[i]-'a']=tmp;
}
p=p->next[s[i]-'a'];
p->sum++;
}
}
void searchtree(char *s)
{
node *p=root;
for(int i=0; i {
p=p->next[s[i]-'a'];
printf("%c",s[i]);
//cout< if(p->sum==1)
break;
}
}
int main()
{
int j,i;
int num=0;
root =new node;
while(cin>>str[num])
{
maketree(str[num]);
num++;
}
for(int i=0; i {
printf("%s ",str[i]);
searchtree(str[i]);
cout< }
return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved