The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

后缀数组学习小节

今天终于将后缀数组总结完了,开个贴庆祝一下,顺便总结一下字符串的相关问题,字符串问题按做法分大概可以是以下几类:
1.暴力brute force ,这个没什么可说的,一般正规的比赛这种方法必然超时。。。(山寨比赛似乎可以考虑。。。)
2.字典树问题,通常和多个字符串的前缀有关。能写出模板基本上就没问题了,比赛的时候稍微改改,套上去就能用。
3.KMP问题,单串匹配,求一个字符串在另一个字符串中的匹配情况,可重复,不可重复均可。Next函数扩展问题,这个我已经总结过。
4.后缀数组问题,重点之所在,结合罗穗骞同学的论文,总结了使用后缀数组的13中重要情况,几乎可以覆盖所有的字符串问题。
5.AC自动机 这个多串匹配,模板很重要。

posted on 2009-09-11 23:25 abilitytao 阅读(377) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理