hdu 1075 What Are You Talking About【字典樹】

這道題就是一道普通的字典樹 把皮卡丘的語言插入字典樹就行 然後每一個皮卡丘的單詞的最後一個字母 标記一下 代表到這裡已經是一個完整的單詞了同時在這個節點記錄皮卡丘語言對應的人類語言就行

Sample Input

START

from fiwo

hello difh

dream riwosf

you fnnvk

like fiiwj

END

START

difh, i’m fiwo riwosf.

i fiiwj fnnvk!

END

Sample Output

hello, i’m from dream.

i like you!

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
struct trie_node
{
	string vlaue;
	bool flag; //用來标記到此節點是不是一個完整的單詞
	trie_node *child[30];
};
trie_node* creat_node()
{
	trie_node *node = new trie_node();
	node->flag = false;
	for (int i = 0; i < 30; i++)
		node->child[i] = NULL;
	return node;

}
void insert_node(trie_node *root, string cs, string sv)//字典樹的插入
{
	int i = 0;
	trie_node *node = root;
	while (i < cs.size())
	{
		if (node->child[cs[i] - 'a'] == NULL)
			node->child[cs[i] - 'a'] = creat_node();
		node = node->child[cs[i] - 'a'];
		i++;
	}
	node->flag = true;
	node->vlaue += sv;
}
string search_trie(trie_node *root, string key)
{//尋找這傻老鼠的話是不是自己的獨特語言
	int i = 0;
	trie_node *node = root;
	while (i < key.size())
	{
		if (node->child[key[i] - 'a'] == NULL)
			return key;//這裡先比較 可以提前判斷一下是不是它的話
			//看看這個單詞存不存在字典樹裡面 注意 不确定是不是老鼠的話
			//比如 字典樹裡面有一個是abcde  但是查詢abc的時候 abc是可以找到的
			//這裡需要注意下 我就是掉這個坑裡面了
		node = node->child[key[i] - 'a'];
		i++;
	}
	if (node->flag == (true))//這時候代表是自己的獨特語言 傳回翻譯後的話
		return node->vlaue;
	return key;//不是那就傳回未翻譯的單詞
	//最後這裡開始沒加 忘記這裡了一直報wrang 但是感覺應該是報運作錯誤的
	//可惜了
}
int main()
{
	trie_node *root = creat_node();
	string be = "START";
	string en = "END";
	string sbe, st, svlaue;
	cin >> sbe;
	while (cin >> svlaue)
	{
		if (svlaue == en)
			break;
		else
		{
			cin >> st;
			insert_node(root, st, svlaue);
		}
	}
	cin >> sbe;
	getchar();
	while (getline(cin, st))
	{
		if (st == en)
			break;
		string lasts, ts;
		int len1 = st.size();

		//cout << st.size();
		int i;
		for (i = 0; i < len1; i++)
		{
			//cout << i << endl;
			if ('a' <= st[i] && st[i] <= 'z' )
			{
				ts += st[i]; // if語句用來判斷連續的字母
			}
			else//到這裡 此時的st[i]存儲的是标點符号或者空格 代表前面的字元是一個單詞了
			{
				lasts += search_trie(root, ts);//然後去字典樹裡面查找有沒有這老鼠說的話
				lasts += st[i];//把空格或者符号也加進去就行
				ts.clear();//清一下ts 待會重新記錄單詞
			}
		}
		//if (!ts.empty())//這裡面是我開始試資料的時候 防止最後一個字元是字母的時候準備的
		//但是估計沒啥用
		//	lasts += search_trie(root, ts);
		//試了一下 看來可以 題目給的格式還是很标準的wrang的同學這裡不是坑點
		cout << lasts << endl;
	}
}