字符串——蒟蒻永远的阴影
对于字符串匹配
KMP很好的解决了以一个文本串匹配一个模板串的问题
但如果模板串有多个呢
这是KMP不再适用
我们引入一个新的数据结构——字典树
(当然又有像AC自动机这样更优的)
(但要理解AC自动机,便必须先学会KMP与字典树的思想)
字典树可以将多个单词压缩到一棵树上
这样便减少了对于一个文本串要匹配多个模板串时
要重复匹配相同前缀的弊端
先呈上一张字典树的图解
如图所示
字典树的每条边储存了一个字符
这样从根结点走下来
每个结点便代表一个单词
但特别的,根节点是不表示字符或单词的!!!
然而我们要怎样确定那些结点代表的单词在模板串里出现过呢
所以这里我们给那些代表的单词在模板串里出现过的结点
再插入时就打上一个标记
如图中黄色结点
这里也讲一下字典树的缺点
由于树的每层都要对应有26个字母
那么如果模板串很长
空间开销就会特别大
如果不止小写字母
那么空间开销还会更大
不过一般的题目也不会卡那么紧
下面是字典树的基本操作
字典树结构体
struct node
{
node* nxt[26];//对应下一层字母的指针
bool judge;//判断该单词模板串里出现过
node()//构造函数;初始化
{
judge=false;
for(int i=0;i<26;i++)
nxt[i]=NULL;
}
};
node* rt=new node();//初始根结点
插入
void ins(char ss[])
{
int len=strlen(ss);
node* p=rt;
for(int i=0;i<len;i++)
{
int num=ss[i]-'a';//找到下一层结点
if(p->nxt[num]==NULL)
{
node* k=new node();
p->nxt[num]=k;
}//如果该节点不存在则创建新结点,否则继续迭代插入
p=p->nxt[num];
}
p->judge=true;//单词插入完毕,标记该节点
}
查找/匹配
bool find(char ss[])
{
int len=strlen(ss);
node* p=rt;
for(int i=0;i<len;i++)
{
int num=ss[i]-'a';
p=p->nxt[num];
if(p==NULL) return false;
//如查找过程中有结点不存在,则匹配失败
}
if(p->judge)return true;
//遍历完文本串,若该接点被标记,则查着成功
else return false;//否则查找失败
}
其实插入和查找的代码挺像的不是嘛