本文主要是介绍Trie树静态建树模板,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
关于Trie的静态建树的讲解可以看白书,很简单的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn = 1000010;
const int kind = 26;struct Trie
{int ch[maxn][kind];int val[maxn];int sz;Trie() {sz = 1; memset(ch[0],0,sizeof(ch[0]));}int idx(char c) {return c - 'a';}void Insert(char *s, int v){int u = 0;int n = strlen(s);for(int i=0;i<n;i++){int id = idx(s[i]);if(!ch[u][id]){memset(ch[sz],0,sizeof(ch[sz]));val[sz] = 0;ch[u][id] = sz++;}u = ch[u][id];}val[u] = v;}bool Search(char *s){int u = 0;int n = strlen(s);for(int i=0;i<n;i++){int id = idx(s[i]);if(!ch[u][id]) return 0;u = ch[u][id];}if(val[u]) return 1;else return 0;}
}t;int main()
{int n,m;char s[20];while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++){scanf("%s",s);t.Insert(s,1);}for(int i=0;i<m;i++){scanf("%s",s);if(t.Search(s)) cout<<"FIND\n";else cout<<"NO FIND\n";}}return 0;
}
这篇关于Trie树静态建树模板的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!