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

此篇文章共收到打赏
0

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

发信人: lhict (至少还有我), 信区: Programming
标  题: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Tue Dec  7 12:55:47 2004), 转信

【 以下文字转载自 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: 24.185.]
--
※ 转载:.Unknown Space - 未名空间 mitbbs.com.[FROM: 24.185.]

 
netghost
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: 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.]

 
babbage
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

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

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
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,
where every odd-length substring is a palindrome.










【 在 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


--
Ipso facto delecto!

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

 
babbage
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: 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.]

 
Pront
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: Pront (阿呆), 信区: Programming
标  题: Re: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Thu Dec  9 03:45:15 2004) WWW-POST

我的程序和你的很象,不过我是这么想的:
对一个字符串,从左到右,分别以某个字符(或两个字符的中间)为轴,
然后向两边找对应字符,看看最远能走多少。加起来就是了。

如 “222"

2|2 2
2|2|2
2 2|2

#ifdef WIN32
#pragma warning(disable:4786 4101)
#define min _MIN
#define max _MAX
#endif
#include <vector>
#include <string>
#include <iostream>
using namespace std;

int maxPalindrome(string s)
{
    int i, j, k;
    int count = 0;
    for(i = 0; i < s.size(); i++)
        for(k = 0; k < 2; k++)
            for(j = 1; ; j++)
            {
                int x1 = i + k + j;
                int x2 = i - j + 1;
                if (x2 < 0 || x1 >= (int)s.size()
                    || s[x1] != s[x2])
                {
                    count += j-1;
                    break;
                }
            }
    return count;
}

int main()
{
    cout << maxPalindrome("aa") << endl;
    cout << maxPalindrome("aabb") << endl;
    cout << maxPalindrome("222") << endl;
    cout << maxPalindrome("baaab3") << endl;
    cout << maxPalindrome("aabbaa") << endl;
    return 0;
}



【 在 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
: 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,
: where every odd-length substring is a palindrome.
:
:
:
:
:
:
:
:
:
:
: 【 在 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
:
:






--
※ 修改:·Pront 於 Dec  9 03:45:15 修改本文·[FROM: 24.16.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 24.16.]

 
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 ]
[快速返回] [ 进入葵花宝典讨论区] [返回顶部]
回复文章
标题:
内 容:

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

友情链接


 

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

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