d********w
发帖数: 363 | 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**9
发帖数: 351 | 2 我觉得是对的，有人认为是错的是觉得(find longest common substring of A and B,
自动认为是longest palindromic不对) | l*****a
发帖数: 14598 | 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;i
find 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.
: 有人说是错的，
: 到底那种正确又简洁的方法呢，请大牛指点
| c******e
发帖数: 1032 | | f*******4
发帖数: 1401 | 5 为啥不对？想不通
B,
【在 i**9 的大作中提到】
: 我觉得是对的，有人认为是错的是觉得(find longest common substring of A and B,
: 自动认为是longest palindromic不对)
| f*******4
发帖数: 1401 | 6 面试时候会让你写如何build一个后缀树的代码么。。。。我脚着我是肯定写不出的。
。。
【在 c******e 的大作中提到】
: suffix tree o(n)
| l*****a
发帖数: 559 | 7 还得写个O（n）建树的。
【在 f*******4 的大作中提到】
: 面试时候会让你写如何build一个后缀树的代码么。。。。我脚着我是肯定写不出的。
: 。。
| l*****a
发帖数: 14598 | 8 其实建树好写
关键是make sure that it support O(1) LCA algorithm【 在 forever84 (to be
with you) 的大作中提到: 】 |
|
