分类:未分类

可爱(划死)的字符串算法们

可爱(划死)的字符串算法们

在企鹅学长变态的考纲下,我们无奈中选择一起学习新姿势

first:KMP算法
这是一个小迪更过博客的算法,我就不好意思在这里献丑了,所以献上友链一份:http://rabbithu.xyz/index.php?title=2017-04-01-01

second:Trie树(字典树)
嘤嘤嘤,这就是我在oi小组讲的第一堂课了!?(虽然当天大家都很颓,但是算法的简单是毋庸置疑的!)
在有关字符串的问题中,我们会遇到一些子串啊~前缀啊~的问题,如果正常枚举遍历的话复杂度为O(n*m)(n、m为字串长度),obviously,这很慢!那怎么办呢?
这时候,就有一个十分聪明的人,想到了树!可是树和字符串有啥关系?看图就知道了!

上图这棵树中,边代表字母,结点存储是否是一个单词的结尾,这样我们是不是就可以通过一个26叉树存储任何想要的单词了w!
【如此可知,根节点代表一个空串】

此刻肯定已经有一些人在想怎样代码实现了,链前?显然,如果用链前存储的话,我们无论是插入还是查询都需要在每一层遍历当前字母,这样复杂度岂不是爆炸?所以我们就用一个简单机智的方法实现存儿子的过程!

Trie 的节点可以使用一个结构体进行存储,如下代码中,trans[i]表示这个节点边上字符为i 的转移边所到达的儿子节点编号,若为 0 则表示没有这个儿子。是不是特别喵啊!

插入:若对于一个字符串集合为小写的树中插入一个字符串s

事实上我们只要用O(len)的复杂度,一次存入字母边(检查如果有这条边存在,那么直接下一个,否则建边即可),并且在最后标记是单词的结尾就好了!

查询:查询一个字符串 S 是否是给定字符串集合中某个串的前缀:

这有什么好说的?不和插入是一样的吗!如果没有这条边直接return false就好啊【不附代码了,哼唧!】

最后送上一道例题:POJ 3630
//其中用到了插入、查询同时进行的复杂度优化,简单易懂

如果有小伙伴看到这里,那你可以去尝试一下poj2001 如果没算错的话,只能用指针来实现Trie树
代码如下:

我觉得不会有人看到这里了……
以下是20160603模拟easy round1 T2 震惊

Description
“震惊,OIer熬夜学习可持久化tire树竟是因为……” ——企鹅头条
钫企鹅听说哦艾尔要加入企鹅头条,书写传奇新闻,夺得普利鹅2333年新闻奖。便让他去震惊部去历练一下。
震惊有一些不同的写法,均由小写字母构成,且长度不超过 100100 。比如 : shock,choc,schock 等。每一种震惊的写法,在震惊部拥有不同的权值。
给定 nn 种震惊写法初始的权值,并进行 mm 个操作。
操作分两种 :
1.修改 : 给出一种震惊的写法,若这种写法存在 , 则将这种震惊写法的权值修改为 xx 。
2.询问 : 在 xx 次操作前,某种震惊写法的权值。即若当前为第 dd 次操作 , 则询问第 d−xd−x 次操作后 , 该种震惊写法的权值 。
注意:本题采用强制在线 , 请注意输入输出格式

Input
第一行两个整数 nn , mm 。
接下来 nn 行每行一个字符串 SS ,和一个整数 xx , 分别代表一种震惊的写法和该种写法的初始权值 。
接下来 mm 行每行一个字符串 SS 和一个整数 xx 。字符串 SS 代表一种震惊的写法。
如果本次操作是修改, xx 代表将这种震惊的写法的权值修改为 xx 。
如果本次操作是询问, xx 代表询问 xx 次操作前,这种震惊写法的权值 。
本题采用强制在线,若上次操作的输出为 Er 或 Shock ,则代表本次操作为询问,否则代表本次操作为修改。规定第 11 次操作为修改 。

Output
输出共 mm 行。每行对应一次操作。
对于每组修改,如果修改成功(即存在对应的震惊写法),输出 Ac 。如果不存在对应的震惊写法,输出 Er 。
对于每组询问,如果存在对应的震惊写法,输出对应 xx 次操作前,某种震惊写法的权值 xx 。如果不存在对应的震惊写法,输出 Shock 。

题解:暂割

AC代码:

5+

喜欢该文章的用户:

  • avatar