[POJ3630][HDU1671]Phone List[Trie]

题面

这是一道Trie树模板题. Trie树也叫字典树, 采用类似字典一样的索引方法, 把边看做字符, 把多条字符串建立成树, 达到字符串快速检索, 资瓷插入和查找两个操作.

Trie树的思想一句话概括就是相同的前缀共用同一条链, 在不同的地方产生分支, 在字符串的结束位置打标记. 每个节点有size个指针指向后继, size为字符集大小, 空间复杂度最坏为$latex O(N*size)$, N为总字符数.

插入时扫描要插入的串, 每个节点判断一下是否已经存在, 存在就沿着已有的指针走, 否则就新建节点, 建立指针. 扫完字符串在最后一个节点打标记.

查找时存在指针就沿着走, 扫完字符串时看节点有没有标记, 不存在就这个字符串不存在.

本题可以先把所有字符串插入, 再查询每一个串, 如果在查的过程中没有碰到打的结束标记, 就证明当前串是某个其他串的前缀, 输出NO.

#include<cstdio>
#include<cstring>
#define in inline
#define re register
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b) return -s;
	return s;
}
const int size=100100;
int T,n,trie[size][10],end[size],cnt=1;
in void insert(char s[])
{
	int p=1,l=strlen(s);
	for(re int i=0;i<l;++i)
	{
		if(trie[p][s[i]-48]) p=trie[p][s[i]-48];
		else trie[p][s[i]-48]=++cnt,p=cnt;
	}
	end[p]=1;
}
in bool chk(char s[])
{
	int p=1,l=strlen(s),f=1;
	for(re int i=0;i<l;++i)
	{
		if(end[p]) f=0;
		if(trie[p][s[i]-48]) p=trie[p][s[i]-48];
		else break;
	}
	return f;
}
signed main()
{
	T=read();
	while(T--)
	{
		n=read();
		char s[10002][11];bool f=true;
		for(re int i=1;i<=n;++i){scanf("%s",s[i]);insert(s[i]);}
		for(re int i=1;i<=n;++i)
		{
			f=chk(s[i]);
			if(!f){printf("NO\n");break;}
		}
		if(f) printf("YES\n");
		memset(end,0,sizeof(end));
		memset(trie,0,sizeof(trie));
		cnt=1;
	}
	return 0;
}