Trie 的概念

Trie 又称字典树，前缀树（事实上前缀树这个名字就很好的解释了 Trie 的储存方式）。

Trie 的特点：

Trie 的根节点是空的。
除根节点外，每个节点储存一个字母。
从根节点到每个单词节点的路径上的所有字母连接而成的字符串就是该节点对应的字符串。
每个非叶子结点一般都会被多次使用，以节省遍历时的时间效率。

Trie 是典型的用空间来换时间的做法。插入、查询操作时间复杂度为 $O(n)$ ，其中 $n$ 表示字符串长度。

模板

#define mset(a) memset(a,0,sizeof(a))
const int FOUND=1,VISITED=2,UNFOUND=3; //找到了，重复找，未找到
struct Trie
{
	int index=0;//用以做编号
	struct Node
	{
		int qcnt,exist,etc;//字符串访问次数，是否为字符串等附加信息
        int son[50];//儿子节点
        //字符串这里意为完整的、自根节点到叶子节点组成的字符串
		Node(){mset(son);qcnt=exist=0;}
	}node[500000+10];
	
	int getid(char ch){return ch-'a';}//无需解释
	
	void insert(char s[])//插入操作
	{
		int sons,root=0,len=strlen(s);
		for(int i=0;i<=len-1;i++)
   		{
       		sons=getid(s[i]);
       		if(!node[root].son[sons])
           		node[root].son[sons]=++index;
       		root=node[root].son[sons];
   		}
   		node[root].exist=1;//标记这是个字符串
	}
	
	int find(char s[])//查询操作
	{
   		int sons,root=0,len=strlen(s);
   		for(int i=0;i<=len-1;i++)
   		{
       		sons=getid(s[i]);
       		if(!node[root].son[sons]) return UNFOUND;
       		root=node[root].son[sons];
   		}
   		if(!node[root].exist) return UNFOUND;
   		if(!node[root].qcnt)
   		{
       		node[root].qcnt++;
       		return FOUND;
   		}
   		return VISITED;
	}
}trie;

例题

题面链接：P2580 于是他错误的点名开始了。

题意：给你 $n$ 个字符串以及 $m$ 个询问，每次询问需要回答：如果该询问的字符串没有在 $n$ 个字符串里面出现过，输出WRONG；如果该询问的字符串出现过而且是第一次询问，输出OK；如果该询问的字符串出现过但不是第一次询问，输出REPEAT。

仔细看一下题目，事实上就是 trie 树的模板题。代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define mset(a) memset(a,0,sizeof(a))
	const int FOUND=1,VISITED=2,UNFOUND=3; 
	struct Trie
	{
		int index=0;
		struct Node
		{
			int qcnt,exist,son[50];
			Node(){mset(son);qcnt=exist=0;}
		}node[500000+10];
		
		int getid(char ch){return ch-'a';} 
		
		void insert(char s[])
		{
			int sons,root=0,len=strlen(s);
   			for(int i=0;i<=len-1;i++)
    		{
        		sons=getid(s[i]);
        		if(!node[root].son[sons])
            		node[root].son[sons]=++index;
        		root=node[root].son[sons];
    		}
    		node[root].exist=1;
		}
		
		int find(char s[])
		{
    		int sons,root=0,len=strlen(s);
    		for(int i=0;i<=len-1;i++)
    		{
        		sons=getid(s[i]);
        		if(!node[root].son[sons]) return UNFOUND;
        		root=node[root].son[sons];
    		}
    		if(!node[root].exist) return UNFOUND;
    		if(!node[root].qcnt)
    		{
        		node[root].qcnt++;
        		return FOUND;
    		}
    		return VISITED;
		}
	}trie;
	
	int n,m;
	char name[100];
	void yzmain()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			cin>>name;
			trie.insert(name);
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			cin>>name;
			int jud=trie.find(name);
			if(jud==FOUND) printf("OK\n");
			else if(jud==VISITED) printf("REPEAT\n");
			else printf("WRONG\n");
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}