The Fourth Dimension Space

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

关于罗穗骞《后缀数组——处理字符串的有力工具》论文中的一个BUG

2.2.2子串的个数
例5:不相同的子串的个数(spoj694,spoj705)
给定一个字符串,求不相同的子串的个数。
算法分析:
每个子串一定是某个后缀的前缀,那么原问题等价于求所有后缀之间的不相
同的前缀的个数。如果所有的后缀按照suffix(sa[1]), suffix(sa[2]),
suffix(sa[3]), …… ,suffix(sa[n])的顺序计算,不难发现,对于每一次新加
进来的后缀suffix(sa[k]),它将产生n-sa[k]+1 个新的前缀。但是其中有
height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“贡献”
出n-sa[k]+1- height[k]个不同的子串。
累加后便是原问题的答案。这个做法
的时间复杂度为O(n)。

看的时候怎么都没看懂为什么要加一,从他论文里给出的模板来看,sa[i]的取值应该从0 to n-1,带了一下1111这个数据,显然加一是错误的。后来用模板做了下spoj 694,加1WA,反之AC,证明了我的想法,看来罗同学的表达有些前后不一致了。
另外,罗同学在给出的标程中并没有使用他给出的解法,而是转了个弯,等差数列求和算出所有后缀长度的总和,然后在减去height[i](i from 1 to n),
这个做法比直接累加要好些。

posted on 2009-09-10 19:46 abilitytao 阅读(1180) 评论(0)  编辑 收藏 引用


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