[转载] CS Interview question - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

[转载] CS Interview question

[转载] CS Interview question# Programming - 葵花宝典

l*t2004-12-07 08:12

1 楼

【以下文字转载自 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

n*t2004-12-07 08:12

2 楼

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

【在 l***t 的大作中提到】

: 【以下文字转载自 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

b*e2004-12-07 08:12

3 楼

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) i2) S[i+k] == S[j-k] for all k=0 to j-i. (actually to (j-i)/2 is sufficient.)

b*e2004-12-07 08:12

4 楼

This is A[i][i+1], not A[i][j+1]. (S[i]==S[i+1] means same adjacent chars,
obviously a palin.)
That's why there is a "probably". :)

【在 n******t 的大作中提到】

: 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

P*t2004-12-07 08:12

5 楼

我的程序和你的很象，不过我是这么想的：
对一个字符串，从左到右，分别以某个字符（或两个字符的中间）为轴，
然后向两边找对应字符，看看最远能走多少。加起来就是了。
如　“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
#include
#include
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;

【在 b*****e 的大作中提到】

: 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: 2) S[i+k] == S[j-k] for all k=0 to j-i. (actually to (j-i)/2 is sufficient.)

n*t2004-12-07 08:12

6 楼

是字符操作.不是字符串操作.一般的Ram model.
这个算法主要是建立在suffix tree的处理能力上面.
在建立好suffix tree之后(linear time), 对于每个
LCE的应答在常数时间内可以完成.有兴趣可以查查
suffix tree的算法.

【在 P***t 的大作中提到】

: 我的程序和你的很象，不过我是这么想的：
: 对一个字符串，从左到右，分别以某个字符（或两个字符的中间）为轴，
: 然后向两边找对应字符，看看最远能走多少。加起来就是了。
: 如　“222"
: 2|2 2
: 2|2|2
: 2 2|2
: #ifdef WIN32
: #pragma warning(disable:4786 4101)
: #define min _MIN