当前在线人数17406
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Re: [转载] CS Interview question
[版面:葵花宝典][首篇作者:lhict] , 2004年12月07日12:55:47 ,1153次阅读,5次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页][上页] [下页] [末页][分页:1 2 ]
netghost
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: netghost (dormdaze), 信区: Programming
标  题: Re: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Thu Dec  9 06:36:27 2004), 转信

是字符操作.不是字符串操作.一般的Ram model.
这个算法主要是建立在suffix tree的处理能力上面.
在建立好suffix tree之后(linear time), 对于每个
LCE的应答在常数时间内可以完成.有兴趣可以查查
suffix tree的算法.
【 在 Pront (阿呆) 的大作中提到: 】
: 这个O(n)似乎不是很妥当。如果将一次字符串操作作为一个单位,或许可叫O(n)。
: 但如果对字符操作是多少呢?
: 【 在 netghost (dormdaze) 的大作中提到: 】
: : First We need to define maximum palindrome, which means it is a palindrom
: : but any extension on both side will not make a palindrome.
: : for every such a palindrome with length k has child palindromes
: : of number k/2. So what we need to do is to find all the maxium palindromes.
: : To do this reverse the string S to S'.We say that such palindromes must
: : appears in S'. And further because it is maximum, so suppose it starts from
: : i and end in j with m the middle of it. so S(i-1)!=S(j+1), that means it
: : is the longest common prefix of the suffix of S starting from m and suffix
: : of S' starting from len(S)-m. This is longest common extension problem and
: : could be solved in constant time if a proper generalized suffixed tree is
: : build at first. So we start from m=0 to len(S), calculate all such length
: : out, choose those who >= 0. Thus solve the problems in O(n).
: argument
: cha
: spec


--
※ 修改:.netghost 于 Dec  9 07:04:02 修改本文.[FROM: 212.202.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 212.202.]

 
[首页][上页] [下页] [末页][分页:1 2 ]
[快速返回] [ 进入葵花宝典讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996