> 我用的trie树，输入时gets（）为什么我的程序还是需要800ms。。哪位300ms以内ac的是怎么做的，还是我读数据太慢了阿？

用tried树写的，250MS。请指教，^_^
 /*	poj2503, written by Dream, 2011/4/25	*/
#include<iostream>
#include<cstring>
using namespace std;
const int Max = 260050;
const int branchNum = 26;

struct TriedNode 
{
	char re[12];
	TriedNode *branch[branchNum];
};

TriedNode root;
TriedNode node[Max];
int p = 0;

void Initial()
{
	memset((void*)node, 0, sizeof(node));
}
void Insert(char *word, char *re)
{
	if (NULL == word)
	{
		return;
	}
	TriedNode *location = &root;
	while(*word)
	{
		if (NULL == location->branch[*word - 'a'])
		{
			location->branch[*word - 'a'] = &node[p++];
		}
		location = location->branch[*word - 'a'];
		++word;
	}
	strcpy(location->re, re);
}

void Search(char *res, char *word)
{
	if (NULL == word)
	{
		return;
	}
	TriedNode *location = &root;
	while(*word)
	{
		if (location->branch[*word - 'a'])
		{
			location = location->branch[*word - 'a'];
		}
		else
		{
			strcpy(res, "eh");
			return;
		}
		++word;
	}
	strcpy(res, location->re);
}

int main()
{
//	freopen("input.txt", "r", stdin);
	char word[12];
	char eng[12];
	char res[12];
	char ch = '\0';
	Initial();
	while(scanf("%s%s", eng,word) != EOF)
	{
		Insert(word, eng);
		getchar();
		ch = getchar();
		if ('\n' != ch)
		{
			ungetc(ch, stdin);
			continue;
		}
		break;
	}
	while(scanf("%s", word) != EOF)
	{
		Search(res, word);
		printf("%s\n", res);
	}

	return 0;
};

• 还有ungetc这种东西~学习了 (0) cmonkey 2012-01-27 18:11:51