浅谈字符串匹配算法----字典树Trie

___new2zy___ · 2018-10-12 17:36:51 · 个人记录

浅谈字符串匹配算法----字典树Trie

----谨以此篇来纪念我可怜的字符串水准

本来是不想写字典树的。。。

为了填上我AC自动机的坑也是没办法了

下面我们来看看字典树(Trie)

先上度娘：

字典树，又称单词查找树，键树，Trie树，是一种树形结构，是一种哈希树的变种

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计

优点：查询效率比哈希树高

算法策略：利用字符串的公共前缀减少查询时间，最大限度地减少无谓的字符串比较

根据上面的说明，我们能写出如下的Trie插入代码：

inline void Insert(char *s)//插入单词s
{
    int x=0,len=strlen(s);
    for(int i=0;i<len;i++)
        {
            int y=s[i]-'a';
            if(!tr[x][y])tr[x][y]=++tot;//没有该节点就新建一个
            x=tr[x][y];
        }
    tag[x]++;//最后结尾节点标记一下
}

注意：最开始我们是从根节点0开始遍历的，同时注意最后要标记单词结尾的节点

既然有了插入操作，那么查询操作的代码也很容易得到了：

inline int Search(char *s)//查询单词s
{
    int x=0,len=strlen(s);
    for(int i=0;i<len;i++)
        {
            int y=s[i]-'a';
            if(!tr[x][y])return 0;//没有中间节点显然无解
            x=tr[x][y];
        }
    return tag[x];//返回出现次数即可
}

是不是很类似于插入操作的代码呀

那么到这里，Trie的插入和查询操作就算是讲完了

下面放一下这个例题的完整代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
const int sz=26;
const int maxn=1e5+3;
int tot,tr[sz+3][sz+3],tag[maxn];
inline void Insert(char *s)
{
    int x=0,len=strlen(s);
    for(int i=0;i<len;i++)
        {
            int y=s[i]-'a';
            if(!tr[x][y])tr[x][y]=++tot;
            x=tr[x][y];
        }
    tag[x]++;
}
inline int Search(char *s)
{
    int x=0,len=strlen(s);
    for(int i=0;i<len;i++)
        {
            int y=s[i]-'a';
            if(!tr[x][y])return 0;
            x=tr[x][y];
        }
    return tag[x];
}
int n,Q;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        {
            char s[maxn];
            scanf("%s",s);
            Insert(s);
        }
    Q=read();
    while(Q--)
        {
            char s[maxn];
            scanf("%s",s);
            int sum=Search(s);
            printf("%d\n",sum?sum:-1);
        }
    return 0;
}

对了，如果说是要求某个单词作为所有单词的前缀的出现次数，怎么办呢？

查询仍然不变，我们只需要改动插入的一处即可：

inline void Insert(char *s)//插入单词s
{
    int x=0,len=strlen(s);
    for(int i=0;i<len;i++)
        {
            int y=s[i]-'a';
            if(!tr[x][y])tr[x][y]=++tot;//没有该节点就新建一个
            x=tr[x][y];
            tag[x]++;//只要是前缀，都标记一下
        }
}

这样Trie就支持查询前缀出现次数啦！

讲完了字典树，发现它其实也不是很难

我们可以说，Trie是一种利用公共前缀来达到快速匹配的树形算法

线性的KMP也是一样，也利用了前缀