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

POJ 2001 Shortest Prefixes 字典樹

編輯:C++入門知識

題意很好理解就不說了,然後這道題其實不用字典樹更簡單,但是為了練習trie樹就寫了一下,1A了哈哈,再對比了一下討論區的大神代碼,發現我還是寫復雜了。。。

思路:

想到利用字典樹,繼承字典樹原有機制,從底端葉子向上找,每條路徑最先找

到的分叉點再往下(從葉子找上來的這條路)一個字符即為所求(特殊情況,

如果節點處單詞已結束,那麼就輸出整個單詞好了),也就是從上往下找到的

第一個不是路徑重合(has_same_path = true)的情況或者是is_word =

true的情況,用遍歷二叉樹的方法遍歷整個樹得到所有前綴。
判斷has_same_path的情況很簡單,如果當前tmp->next[num]不為空,則

一定has_same_path
,至於pos則是為了讓答案按順序輸出用的


代碼:


/*
poj      2001
11152K	16MS
*/
#include
#include
#include
#include

#define MAXN 1005

using namespace std;

struct node
{
	node *next[26];
	bool has_same_path;
	bool is_word;
	int pos;
	node()
	{
		memset(next , 0 , sizeof(next));
		has_same_path = is_word = false;
		pos = -1;
	}
}trie[100005];
int trie_num;

struct out
{
	char s[21];
	int pos;
	out()
	{
		memset(s , 0 , sizeof(s));
		pos = -1;
	}
}ans[MAXN];

int n = 1,id;
char str[MAXN][21],tmp_str[21];

bool cmp(out a , out b)
{
	return a.pos < b.pos;
}

void insert(char *s , int pos)//插入單詞 
{
	int len = strlen(s);
	node *now = &trie[0];
	for(int i = 0;i < len;i ++)
	{
		int num = s[i] - 'a';
		if(!now->next[num])
			now->next[num] = &trie[++trie_num];
		else
			now->next[num]->has_same_path = true;
		now = now->next[num];
		if(now->pos == -1)
			now->pos = pos;
	}
	now->is_word = true;
	now->pos = pos;
}

void cons(node *now , int k)//構造答案 
{
	if(!now->has_same_path || now->is_word)
	{
		tmp_str[k] = 0;
		memcpy(ans[++id].s , tmp_str , k);
		ans[id].pos = now->pos;
		now->is_word = false;//防止回溯時再次計入
		if(!now->has_same_path)
			return ;
	}
	for(int i = 0;i < 26;i ++)
	{
		if(now->next[i])
		{
			tmp_str[k] = i + 'a';
			cons(now->next[i] , k + 1);
		}
	}
}

int main()
{
	while(scanf("%s" , str[n]) != EOF)
	{
		insert(str[n] , n);
		n ++;
	}
	n --;
	trie[0].has_same_path = true;
	cons(&trie[0] , 0);
	sort(ans + 1 , ans + n + 1 , cmp);
	for(int i = 1;i <= n;i ++)
		printf("%s %s\n",str[i] , ans[i].s);
	return 0;
}

其實空間沒必要開那麼大,為了省事就亂開了

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