作用
字典树作用正如其名,就是用来找字符串的。先给你一堆字符串作为字典,然后给其他字符串看这些字符串是否在开始给的字符串里,可能对于这种情况首先想到的便是map,但map查找效率十分低下,碰到大量的数据时很容易TLE,于是字典树便到了我们眼前
基本
它实际上就是一个树,类似于求前缀码,用第一层表示第一个字母,第二层表示第二个字母,以此类推,而每个字母不一定都有,这样便减小了搜索所需时间

在计算机中,trie树可以用一个二维数组a[i][j]来表示。第一个元素i
另外还有一个问题是这么多单词,怎么知道这个单词是不是终点呢?,可以通过insert函数中的ch[u][c]=sz++;
来判断,如果等于一,则说明这是终点,
代码实现:

模板
#include<bits/stdc++.h> #define CLR(x) memset(x,0,sizeof x) using namespace std; const int maxnnode=1000; const int maxn=1000;
struct Trie{ int ch[maxnnode][26]; int val[maxnnode]; int sz; void Clear(){sz=1;CLR(ch[0]);CLR(val);} int idx(char c){return c-'a';} void Insert(const char*s,int v){ int u=0,n=strlen(s); for(int i=0;i<n;i++){ int c=idx(s[i]); if(!ch[u][c]) { CLR(ch[sz]); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; } bool Find(const char* s){ int u=0,n=strlen(s); for(int i=0;i<n-1;i++){ int c=idx(s[i]); if(!ch[u][c]) return false; u=ch[u][c]; } int c=idx(s[n-1]); if(val[ch[u][c]]) return true; return false; } };
Trie T;
int main() { T.Clear(); int n,m; scanf("%d%d",&n,&m); char tmp[maxn]; for(int i=1;i<=n;i++) { scanf("%s",tmp); T.Insert(tmp,i); } for(int i=1;i<=m;i++) { scanf("%s",tmp); if(T.Find(tmp)) printf("Found!\n"); else printf("Not Found!\n"); } return 0; }
|