字符串（存储系列）

sLMxf · 2024-02-05 13:29:10 · 算法·理论

什么是字符串呢？就是一堆字符的东西。很容易想到用 char s[MAXN] 定义。

这里介绍一种新的数据结构：string。

如果要定义一堆字符串呢？用 string s[MAXN] 就可以了。

不过给定另一种定义方式——字典树（Trie）

先来看看字典树是怎么定义的。例如这几个字符串：iak，ioi，iakioi，ioiakme。

字典树上用边存贮每个字符，用每个简单路径存储每个字符串。如上图。

例如：魔族密码。

字典树的加入：

void insert(string s)
{
    int u=1;//根 
    int len=s.size();
    int res=0;
    for(int i=0;i<len;i++)
    {
        int z=s[i]-'a'+1;
        if(trie[u][z]==0)
            tot++,trie[u][z]=tot;
        u=trie[u][z];
        res+=word[u];
    }
    word[u]++,res++;
    ans=max(res,ans);
}

使用 insert(s) 插入字符串 s。

字典树就是这样定义的。如果还想知道更多算法，就见字符串（easy-2）吧。