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.
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
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; }