听ghost讲那字典树(trie)与AC自动机的事情

Written by 韩光 in 束发戎马 on 五 09 十月 2009. Tags: NOIP, 数据结构, 自动机,

吐个槽先:名字好长!为什么那么长!保持用一格式就那么重要吗!

1.字典树:

字典树,顾名思义,就是把一坨单词以某种树型结构储存起来,当你在这棵树中找寻某个单词的时候,就像查字典一样,一个字母一个字母地筛除不需要的序列。

要实现字典树的这个功能,就需要将有相同前缀的单词存在同一条树枝上,这样一来,字典树除根以外的每个节点都是一个字母(根为空节点),分别以它们为结尾,均可以从树的根开始走出一条字符序列。再标记每个可被视为单词的序列的结束节点,一棵香喷喷的字典树就新鲜出炉啦!这种储存减少了冗余数据的存储,节省空间;查找的时候减少了重复子串的查找,降低了时间复杂度 …

Continue reading »


md5加密算法c语言实现

Written by 韩光 in 披坚执锐 on 日 13 九月 2009. Tags: 密码学, 信息安全,

从网上找的md5信息摘要算法的c语言实现,因为我不会用Pascal语言一二进制形式打开文件,就只能把这个c语言的代码原封不动地(其实还是我自己抄了一遍,把编码风格改得比较像自己的)粘到qq空间上来,以做珍藏,具体的实现原理我就不再赘述了,总结起来就是补位,加长度,分组,位运算,反向输出这么几步。 所谓md5信息摘要算法,当然比他的前身md4信息摘要要先进,升级的地方主要有这么几点: 1.定义的宏里面,I函数由原来的(x ^ y^ z),也就是Pascal中的(x xor …

Continue reading »


zoj1013

Written by 韩光 in 束发戎马 on 日 06 九月 2009. Tags: NOIP, ZOJ, 翻译,

哈哈,第二道题的翻译……寂寞……新鲜出炉了!

改了一些题目背景,但是要写的东西还是一样的。

很久很久以前,恩洛斯王国住着一位女王,她的名字叫作Sylvanas Windrunner(希尔瓦娜斯.追风者)。有一天,女王得知她的父亲去世的噩耗,万般悲痛之中,她踏上了参加父亲葬礼的航程。以防万一,她征集了一支禁卫舰队来护航。当她到达目的地--艾拉西亚的时候,她发现了联盟的一座防御塔,那座塔已被战火焚毁。希尔瓦娜斯女王从秘密渠道得知:她的父亲是被一位死亡骑士用毒酒害死的,这使得希尔瓦娜斯女王开始了复仇行动 …

Continue reading »


zoj1011

Written by 韩光 in 束发戎马 on 六 05 九月 2009. Tags: NOIP, ZOJ, 翻译,

老师让做zoj1011上的题,苦于那里都是英文题目,有的大牛用在线翻译站点翻译了一下,让我们更深刻地感觉到“翻译即背叛”……尤其是用电脑翻译……………………

为了使背叛的程度尽可能地减小,咱小菜来人工翻译了一遍,应该还是能读通的把,不通顺或者对题意不明的童鞋,可以留言或者与我qq联系。

我翻译的不是试题,是寂寞…………

非判断性树型自动机(NTA)是一种由多个树型结构组成的设备。每种设备在自己的一种特定的规则下运行,依据这种规则设备中的每个树型结构可以产生一系列的信号,这些信号可以组成一个信号系统。在这个系统里面,其中一个信号叫做“开始信号”,还有一些信号叫做“可接受信号”,其他的信号叫做 …

Continue reading »