贡献者: 有机物
假设要存储这些字符串:
cat
、her
、him
、no
、nova
。
对应在图上就长这样:
插入字符串:从根结点开始看,看有没有这个字母,有的话就走,没有的话就创建一个新的字母结点。存储每个单词一般都会在这个单词的结尾字母打一个标记(如图中的蓝色结点),意思是以这个字母为结尾的路径是有一个单词的。插入一个字符串动图
查找字符串:比如要查找 him
这个单词,我们就从根结点开始走,依次走每个字母,如果找到了要查找的字符串的结尾字母并且这个结点上有标记,就表示找到了这个字符串。查找字符串动图
来看一个具体题目:维护一个字符串集合,支持两种操作:
I x
向集合中插入一个字符串 x;
Q x
询问一个字符串在集合中出现了多少次。
共有
开一个数组 sno[N][26]
来表示每个点的所有儿子,第一维存储结点大小,第二维存储每个字母,因为字符串仅包含小写英文字母,所以第二维只开 cnt[N]
表示以当前字母为结点的字母有多少个(标记)idx
的含义和链表里的 idx
含义一样。
友情链接: 超理论坛 | ©小时科技 保留一切权利