1, Basic concepts

Trie (dictionary tree) is a multi tree structure used to realize fast string retrieval. Each node of tier has several character pointers. If a character c is scanned when inserting or retrieving a string, it will follow the C character pointer of the current node to the node pointed to by the pointer.
  initialization:
   an empty Trie contains only one root node, and the character pointer of this point points to null.

  insert:
   when we need to insert a string S, we make a pointer p initially point to the root node. Then, scan each character c in S in turn:
   (1) if the c character pointer of P points to an existing node Q, let P=Q.
   (2) if the c character pointer of P points to null, create a new node Q, make the c character pointer of P point to Q, and then make P=Q.
   when the character in S is scanned, mark it as the end of a string on the current node P.

  search:
   when we need to retrieve whether a string S exists in Trie, we make a pointer P point to the root node at first, and then scan each character c in S in turn:
   (1) if the c character pointer of P points to null, it indicates that S has not been inserted into Trie and ends the retrieval.
   (2) if the c character pointer of P points to an existing node Q, let P=Q.
   when the characters in S are scanned, if the current node P is marked as the end of a string, it indicates that S exists in Trie; otherwise, it indicates that S has not been inserted into Trie.

2, Example 1: P2580 so he started the wrong roll call

This question can be written directly with STL heavy map. For exercise, use dictionary tree.

Title Link

Question surface:

code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
const int maxn=10100;
const int len=50;
int t[maxn*len][26];
int ed[maxn*len];
int tot=1,root=1;

char str[maxn];

void _insert(void)
{
	int slen=strlen(str+1);
	int p=root;
	for(int i=1;i<=slen;i++)
	{
		int ch=str[i]-'a';
		if(!t[p][ch]) t[p][ch]=++tot;
		p=t[p][ch];
	}
	ed[p]=1;
}

int _find(void)
{
	int slen=strlen(str+1);
	int p=root;
	for(int i=1;i<=slen;i++)
	{
		int ch=str[i]-'a';
		if(!t[p][ch]) return 0;
		p=t[p][ch];
	}
	return ed[p]++;
}

int main(void)
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		_insert();
	}
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",str+1);
		int pos=_find();
		if(pos==0) printf("WRONG\n");
		else if(pos==1) printf("OK\n");
		else printf("REPEAT\n");
	}
	return 0;
}
 

III. example 2: P1481 demon family password

Title Link

Question surface:

Code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
const int maxn=2100;
const int len=75;
int t[maxn*len][26];
int ed[maxn*len];
int tot=1,root=1;

char str[maxn];

void _insert(void)
{
	int slen=strlen(str+1);
	int p=root;
	for(int i=1;i<=slen;i++)
	{
		int ch=str[i]-'a';
		if(!t[p][ch]) t[p][ch]=++tot;
		p=t[p][ch];
	}
	ed[p]=1;
}

int dfs(int p)
{
	if(p==0) return 0;
	int maxx=0;
	for(int i=0;i<26;i++)
	{
		maxx=max(maxx,dfs(t[p][i])+ed[p]);
	}
	return maxx;
}

int main(void)
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		_insert();
	}
	printf("%d\n",dfs(root));
	return 0;
}