当前在线人数18232
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:Re: [转载] CS Interview question
[同主题阅读] [版面: 葵花宝典] [作者:netghost] , 2004年12月07日21:49:10
netghost
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: netghost (dormdaze), 信区: Programming
标  题: Re: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Tue Dec  7 22:29:46 2004), 转信

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).


【 在 lhict (至少还有我) 的大作中提到: 】
: 【 以下文字转载自 JobHunting 讨论区 】
: 【 原文由 lhict 所发表 】
: Create a function findPalin() that takes a string of characters as argument
: and returns the number of palindromes (a string in which the sequence of cha
: racters is the same forwards and backwards) in that string. There is no spec
: ial character. This function should be as fast as possible.
: Ex:
: "aa" returns 1
: "aabb" returns 2
: "222" returns 3
: "baaab3" returns 4


--
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 212.202.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

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

友情链接


 

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

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