hdoj1251——用第二种静态trie写法解决

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Trie{
	int v;
	int next[27];
}Trie;
Trie trie[10000000];
int sz=1;
void init()
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	trie[0].v=0;
	return;
}
void insert(char s[])
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
			trie[p].v++;
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].v=1;
		}
	}
	return;
}
int find(char s[])
{
	int i;
	int p=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x])
			p=trie[p].next[x];
		else
			return 0;
	}
		return trie[p].v;

}
char query[1000010];
int main()
{
	char word[20];
	init();
	gets(word);
	while(word[0]!='\0' && word[0]!=' ')
	{
		insert(word);
		gets(word);
	}
	while(gets(query))
	{
		int ans=find(query);
		printf("%d\n",ans);
		

	}
system("pause");
return 0;
}

hdoj1305

题意:如果其中一个字符串是另一个的前缀,则非法。判断一组字符串是否非法。
显然是trie树,考虑以下情况就能AC:
(1)插入时,结点已存在,且是单词结点
(2)插入单词的最后一个结点时,该结点已存在。
以上两种情况都是非法的。

poj2001

两点收获:
1.scanf()读取字符串时,EOF也算一个;用gets()读取字符串时,NULL行也算一个,所以注意读取的个数要减一
2.实在无法AC时,把gets()换成scanf()试试。。。~

hdoj1671

如何判断一个单词是另一个单词的前缀?
可以为trie结点增加一个count域,初始化为0.当插入一个单词时,令它经过的结点的count都自增1.这样如果单词A是单词B的前缀,则单词结点A的count=2。如果一个单词不是任何其他单词的前缀,则该单词结点的count必为1,这是显然的。

hdoj1075

突然发现,做trie树的题,难的不是trie树本身,反而是字符串的处理部分比较繁琐。做了这题,感觉自己在字符串处理方面又有了一些小收获。
将一行文本中的非单词原样输出,单词转换后输出,可以另设一个短字符串,遍历文本串,如果读到的是字母,则加入短字符串;如果读到的不是字母,则检查段字符串是否为空,不空则加上’\0′然后从字典中找,打印该单词后,再打印前面正在遍历的非字母,不然,则直接打印该非字母。

hdoj1247

这题调试了一整天,相死的心都有了,用静态和动态trie都写了一遍,最后终于找到了错误的地方:在分拆字符串后如果找到了一种方案符合条件没有及时break。这样的后果就是如果一个单词可以分解成多种方案(两个单词),那么如果不及时break,会导致该单词打印两遍(甚至多遍)。
另外我觉得这题数据和题意有些不搭,像hat、hatahat这种情况,hathat不应被打印。一个单词分拆后的两个子单词不仅应该出现在字典中,而且应当不同,这才符合题意。(A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.)(可是我考虑这点反而会WA)
最后,学到一点字符串操作的新知识,把一个字符串分成两个子串可以这样做(相关代码参考了别人),充分利用了字符串以’\0′结尾,以及指针的灵活。

Trie链表实现(动态建树)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Trie{
	int v;
	struct Trie* next[27];
}Trie;
Trie* root=(Trie*)malloc(sizeof(Trie));
void insert(char s[])
{
	int i,len=strlen(s);
	Trie *p=root,*q;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];
		}
		else
		{
			q=(Trie*)malloc(sizeof(Trie));
			q->v=0;
			for(int j=1;j<=26;j++)
				q->next[j]=NULL;
			p->next[x]=q;
			p=q;
		}
	}
	p->v=1;
	return;
}
int find(char s[])
{
	int i,len=strlen(s);
	Trie* p=root;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];	
		}
		else
			return 0;
	}
	return p->v;//如果单词不存在,但作为某个单词的前缀存在字典树中,则v=0,返回0,结果正确
}
void del(Trie*root)
{
	int i;
	for(i=1;i<=26;i++)
		if(root->next[i])
			del(root->next[i]);
	free(root);
	return;
}
int main()
{
	int i;
	for(i=1;i<=26;i++)
		root->next[i]=NULL;
	root->v=0;
/*

	char s[100];
	int n,m;
	scanf("%d",&n);
	getchar();
	while(n--)
	{
		gets(s);
		insert(s);
	}
	scanf("%d",&m);
	getchar();
	while(m--)
	{
		gets(s);
		if(find(s))
			printf("found it\n");
		else
			printf("error\n");
	}

*/
	del(root);
system("pause");
return 0;
}

trie模板(find()自己写的,如有错误,概不负责~)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1000000
typedef struct trie{
	int ch[maxn][27];
	int v[maxn];
	int sz;
	trie()//trie最好定义成局部变量,这样对于多case的题目每次都会执行构造函数,这样可以保证使用trie前初始化正确
	{
		int i;
		v[1]=0;
		for(i=1;i<=26;i++)
			ch[1][i]=0;
		sz=1;
	}
	void insert(char s[])
	{
		int i,j;
		int len=strlen(s);
		int u=1;
		for(i=0;i<=len-1;i++)
		{
			int x=s[i]-'a'+1;
			if(ch[u][x]==0)
			{
				sz++;
				for(j=1;j<=26;j++)
					ch[sz][j]=0;
				v[sz]=0;
				ch[u][x]=sz;
			}
			u=ch[u][x];
		}
		v[u]=1;
		return;
	}
	bool find(char s[])
	{
		int i,j;
		int u=1;
		int len=strlen(s);
		for(i=0;i<=len-1;i++)
		{
			int x=s[i]-'a'+1;
			if(ch[u][x]==0)
				return false;
			else
				u=ch[u][x];
		}
		if(v[u]==1)
			return true;
		return false;
	}

}trie;
int main()
{
	


system("pause");
return 0;
}