学步园

tyvj 1228:

字典树。

#include <stdio.h>
#include <string.h>

struct node
{
	char *s;
	bool f;//单词结束的标志 
	node *next[26];
	node()
	{
		int i;
		for(i = 0; i < 26; i++)
			next[i] = NULL;
		f = 0;
	}
};

void build(node *head, char str[])
{
	node *temp = head;
	int i, len = strlen(str), j;
	for(i = 0; i < len; i ++)
	{
		int t = str[i] - 'a';
		if(temp->next[t] == NULL)
		{
			node *e = new node;
			//for(j = 0; j <= i; j++)
			//	e->s[j] = str[j];
			//e->s[j] = '\0';
			temp->next[t] = e;
		}
		temp = temp->next[t];
	}
	//单词读入结束，将整个单词放入s指向的数组中 
	//方便输出，也比较省内存 
	temp->f = 1;
	temp->s = new char[25];
	strcpy(temp->s, str);
}

int flag;
void search(node *temp)
{
	int i;
	if(flag >= 8)
		return;
	if(temp ->f == 1)
	{
		if(flag == 0)
			printf("%s", temp->s);
		else
			printf(" %s", temp->s);	
		flag ++;
	}
	for(i = 0; i < 26; i++)
		if(temp->next[i] != NULL)
			search(temp->next[i]);
	return ;
}

/*
比较麻烦的输出字典树 
char xx[25];
void dfs(node *temp, int len)
{
	int i;	
	if(temp->f == 1)
	{
		xx[len] = '\0';
		printf("%s\n", xx);
	}
	for(i = 0; i < 26; i++)
	{
		if(temp->next[i] != NULL)
		{
			xx[len] = i + 'a';	
			dfs(temp->next[i], len + 1);
		}
	}
}
*/

void dfs(node *temp, int len)
{//输出字典树中的单词 
	int i;	
	if(temp->f == 1)
		printf("%s\n", temp->s);
	for(i = 0; i < 26; i++)
		if(temp->next[i] != NULL)
			dfs(temp->next[i], len + 1);
}


int main (void)
{
	int n;
	scanf("%d", &n);

	node *head = new node;
	char str[25];
	int i;
	for(i = 0; i < n; i++)
	{
		scanf("%s", str);
		build(head, str);
	}
	//dfs(head, 0);	
	scanf("%d", &n);
	while(n --)
	{
		flag = 0;
		scanf("%s", str);
		int len = strlen(str);
		node *temp = head;
		for(i = 0; i < len; i++)
		{
			if(temp ->next[str[i] - 'a'] != NULL)
				temp = temp ->next[str[i] - 'a'];
			else		
			{//不存在以输入单词为前缀的单词 
				printf("%s\n", str);
				flag = 1;
				break;
			}
		}
		if(flag == 0)
		{
			search(temp);
			printf("\n");			
		}
	}
	return 0;
}