注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

【挖坑】后缀系列专题  

2014-08-14 14:51:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

声明:

1.本系列文章用于备忘(主要)和回(bao)馈(fu)社会(可能性不大,毕竟我这么弱)。

2.借此系列文章D我的人请出门左转。

3.本系列文章为完全公开,转载请注明出处(应该没多少人看,转载应该更是没有了)

4.如果本系列文章涉及侵权,请及时指出。



考虑这样一个问题:

有一文本串,长度为m(m<=10W)

以及n个询问,每个询问给出一个字符串s(|s|<=1W),求s在文本串中出现了几次。


大蒟蒻mxh:我会AC自动机我自豪!


但是……

【醒目】强制在线【醒目】

于是AC自动机就萎掉了QAQ、


我们需要基于文本串的预处理。

考虑到子串=后缀的前缀,以及trie可以快速匹配前缀。

我们想到下面一个算法:

把文本串的所有后缀都塞进一个trie里,然后就可以快速查找了。

但是……这样时空复杂度都是O(n^2)的……太慢了太慢了太慢了太慢了太慢了太慢了。

我们需要优化!

于是我们有了下面几种东西:


后缀数组

后缀树【待填】(大约这星期能填完)

后缀自动机【待填,很可能不会填了……】(我不知道什么时候会填)

后缀二叉搜索树【这是什么东西我不会】

(Ruchiose:后缀二叉搜索树就是用一个替罪羊树来搞后缀,每个后缀弄一个变量,这样就可以O(1)比较两个后缀了,插入的时候我们就~!@#¥%&*……然后我们就可以O(1)比较一个后缀,O(logn)插入了。大蒟蒻mxh:听不懂o(≧口≦)o 

具体可以问@Ruchiose)


  评论这张
 
阅读(8)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018