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

发信人: babbage (tm), 信区: Programming
标  题: Re: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Wed Dec  8 23:02:46 2004), 转信

【 在 netghost (dormdaze) 的大作中提到: 】
: 【 在 babbage (tm) 的大作中提到: 】
: : Let's say that the input string is S, S[1]..S[N] are the chars.
: : The question is to find all pairs (i,j) such that:
: : 1) i<j, and
: : 2) S[i+k] == S[j-k] for all k=0 to j-i. (actually to (j-i)/2 is sufficient.)
: : -- this is the same as saying S[i..j] is a palindrome.
: : Let us use boolean array A[i][j] to store if S[i..j] is a palin, then
: : we have:
: : 1) A[i][i]=true, and
: : 2) A[i][i+1]=true iff S[i]=S[i+1], and
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: A[i][j]?This is not true, A[i][j+1] could be true, even s[i][j]
: are not palin.

This is A[i][i+1], not A[i][j+1]. (S[i]==S[i+1] means same adjacent chars,
obviously a palin.)

: : 3) A[i][j]=true iff A[i+1][j-1] is true && S[i]==S[j]
: : So we can use 1) and 2) to initialize all, A[i][i] and A[i][i+1]
: : and use 3) as the dynamic programming step when j>=i+2:
: : /* 1 */ for k=2 to N-1   // k is (j-i)
: : /* 2 */   for i=1 to N-k
: : /* 3 */     A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j])
: : Now we know if S[i..j] is a palindrome! It takes O(N^2) time.
: : This is probably optimal. Because there are strings that contains O(N^2)
: : palindromes, for example, S= "ABABABABAB...."   (N repetitions of AB,
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: This is not true, because it contains N^2 palins does not mean you need
: N^2 to get the number.

That's why there is a "probably". :)

: : where every odd-length substring is a palindrome.


--
Ipso facto delecto!

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

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

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

友情链接


 

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

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