Why so serious? --[NKU]schindlerlee

2010-06-21 20:10:05 关于Aho-Corasick (AC) 自动机的三道题目

昨天学习了一下AC自动机是什么东西,做了三道题
至于AC自动机的详细解释和资料可以通过搜索 Aho Corasick 找到很多相关论文和资料,我就不要班门弄斧了。
第一道hdu 2222,AC自动机的基本是用方法,直接应用在多模式匹配上。
第二道pku 2778 利用AC自动机减少状态量,之后将状态转移做成矩阵,利用矩阵的二分乘法得到log级别的复杂度。
第三道pku 3691 使用同样是利用AC自动机减少状态量,由于状态数太大不可能实现的dp,变成可能。

下面是后两个题的代码。
pku2778

pku3691

posted on 2010-06-21 20:13 schindlerlee 阅读(1737) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理