最近随洛谷日报看了一下Trie树，来写一篇学习笔记。
Trie树：支持字符串前缀查询等（目前我就学了这些qwq）
一般题型就是给定一个模式串，几个文本串，询问能够匹配前缀的文本串数量。
首先，来定义下Trie树:其根节点为空，定义如下数组：
#include#include #include #include using namespace std;int trie[500000][30],p[500000];//trie[u][x]用来表示u串中x字符所指的节点编号char ch[500000];//ch数组是字符串，每次插入，p数组是标记数组，插入完后打标记int main(){ return 0;}
下面给出插入代码：
#include#include #include #include using namespace std;int trie[500000][30],p[500000]tot;char ch[500000];inline void Insert(char *ch){ int u=0,len=strlen(ch+1); for(int i=1;i<=len;++i){ int x=ch[i]-'a';//具体情况具体分析 if(!trie[u][x])trie[u][x]=++tot;//编号新建 u=trie[u][x]; }p[u]=1;ch//标记 }int main(){ return 0;}
那么，如果我们要查询已知串中有没有当前文本串或前缀，如何做？
每次匹配，如果没有匹配完trie便指向0了，return 0即可。
代码：
#include#include #include #include using namespace std;int trie[500000][30],p[500000]tot;char ch[500000];inline void Insert(char *ch){ int u=0,len=strlen(ch+1); for(int i=1;i<=len;++i){ int x=ch[i]-'a';//具体情况具体分析 if(!trie[u][x])trie[u][x]=++tot;//编号新建 u=trie[u][x]; }p[u]=1;ch//标记 }inline int query(char *ch){ int u=0,len=strlen(ch+1); for(int i=1;i<=len;++i){ int x=ch[i]-'a'; if(!trie[u][x])return 0; u=trie[u][x]; } return 1;//return p[u];}int main(){ return 0;}
持续更新中。