[学习笔记] 字典树

https://blog.csdn.net/qq_49688477/article/details/118879270 字典树图文详解

就是根据“查字典”的思想使用 c++ 实现罢了。

比如要查一个单词 \(\texttt{fAKe}\)，先在根节点中查找 \(\texttt{f}\)，找不到则没有这个单词。找到了就来到 \(\texttt{f}\) 的节点往下查找 \(\texttt{A}\)，以此类推就好了。同样，也可以查找这个单词是否属于另一个单词的前缀。

#include<bits/stdc++.h>
using namespace std;
int trie[100010][210],id;
void insert(string st)
{
	int res=0;
	for(int i=0;i<st.size();i++)
	{
		if(trie[res][st[i]]==0)
			trie[res][st[i]]=++id;
		res=trie[res][st[i]];
	}
}
bool find(string st)//这里的查找是前缀依旧可行的
{
	int res=0;
	for(int i=0;i<st.size();i++)
	{
		if(trie[res][st[i]]==0)
			return false;
		else res=trie[res][st[i]];
	}
	return true;
}
int main()
{
	insert("fuckccf");
	cout<<find("fuck");
	return 0;
}