模板
luogu P8306
支持API:
-
insert(word)添加单词 -
search(word)查询单词出现了几次 -
prefixNumber(pre)查询前缀 -
deletd(word)删除单词，若不存在则无事发生 -
clean()初始化
下面是一个仅支持数字，大、小写英文字母的实现
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e7+5;
struct Trie{private:int T[N][26+26+10];int pass[N];int end[N];int cnt=1;public:int getnex(char x){if(x>='0'&&x<='9')return x-'0';if(x>='a'&&x<='z')return x-'a'+10;return x-'A'+36;}void insert(string word){int cur=1;pass[cur]++;for(char x:word){int nex=getnex(x);if(T[cur][nex]==0){T[cur][nex]=++cnt;}cur=T[cur][nex];pass[cur]++;}end[cur]++;}int search(string word){int cur=1;for(char x:word){int nex=getnex(x);if(T[cur][nex]==0)return 0;cur=T[cur][nex];}return end[cur];}int prefixNumber(string pre){int cur=1;for(char x:pre){int nex=getnex(x);if(T[cur][nex]==0)return 0;cur=T[cur][nex];}return pass[cur];}void deletd(string word){if(search(word)==0)return;int cur=1;for(char x:word){int nex=getnex(x);if(--pass[T[cur][nex]]==0){T[cur][nex]=0;return;}cur=T[cur][nex];}end[cur]--;}void clean(){for(int i=1;i<=cnt;++i){pass[i]=0;end[i]=0;memset(T[i],0,sizeof(T[0]));}cnt=1;}
}ct;