最长回文串 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

最长回文串

最长回文串# JobHunting - 待字闺中

d*w2011-01-25 08:01

1 楼

应该是老题了，http://www.careercup.com/question?id=245679 讨论了半天，
比如这种：
1. Original string is A
2. Reverse string is B
3. Find common strings are C, D, E ....
4. Find palindromic strings in step 3, suppose C, D.
5. Find the max length of strings in step 4. Return.
有人说是错的，
到底那种正确又简洁的方法呢，请大牛指点

i*92011-01-25 08:01

2 楼

我觉得是对的，有人认为是错的是觉得(find longest common substring of A and B,
自动认为是longest palindromic不对)

l*a2011-01-25 08:01

3 楼

你这个复杂度是多少？
有一种O(N2)很直接的
string is a[0]..a[n-1],
assume a[i] (i=1..n-2) is the middle(or a[i+1])
judge whether a[i+k]==a[i-k] then k++ or get the
longest palindrome with center a[i]...
最快的是generalized suffix tree,O(N),but need extra space
store A and reverse string B in the GST,
for(i=1;ifind max LCA(a[i],b[n-1-i])and LCA(a[i],b[n-i])

【在 d********w 的大作中提到】

: 应该是老题了，http://www.careercup.com/question?id=245679 讨论了半天，
: 比如这种：
: 1. Original string is A
: 2. Reverse string is B
: 3. Find common strings are C, D, E ....
: 4. Find palindromic strings in step 3, suppose C, D.
: 5. Find the max length of strings in step 4. Return.
: 有人说是错的，
: 到底那种正确又简洁的方法呢，请大牛指点