I**A
发帖数: 2345 | 1 有没有什么好办法？
我能想到的就是最笨的法子,need O(n^2) time |
s*******s
发帖数: 46 | |
I**A
发帖数: 2345 | 3 (1)
ababcdbaba
after reverse
ababdcbaba
abab (or baba) is the common sequence, but it is not palindrome.
(2) how to get 最长公共字序列 of two strings effectively?
thanks thanks
【在 s*******s 的大作中提到】
: 反过来，比较最长公共字序列
|
s*******s
发帖数: 46 | 4 1.比较最长公共子序列可以用dp啊 复杂度m*n m,n是两个串的长度
2.第一个确实是个好例子，我觉得可以把问题变成求第一个字母序列是逆序最后一个字
母序列的最长子序列。你把第一步里的二维表打出来的话，这个也很好解决的了。 |
f*******r
发帖数: 1086 | 5 common substring的方法是有问题的，比如
下面这个input:"abcdecba"
以下这个link给了一个正确的方法:
http://github.com/stevekrenzel/Miscellaneous/blob/9a5d71051b2c3caffdf85a5c96
30b85bd177aebc/palindrome/palindrome.py
以下是我自己用这个方法写的code，效率是O(N^2)
//O(N^2)
void FindLongestPalindrome(char* a)
{
if(a==NULL) return;
int iLen = strlen(a);
if(iLen == 0) return;
int iStartIdx = 0;
int iEndIdx = iLen-1;
int iMaxLength = 0;
int iMaxIdxStart = 0;
int iMaxIdxEnd = 0;
/
【在 s*******s 的大作中提到】
: 反过来，比较最长公共字序列
|
I**A
发帖数: 2345 | 6 那个link给的solution就是最笨的法子
复杂度是O(n^2)
反正reverse了之后再找common substring, 也是O(n*n)
估计也就不要折腾了。。。
【在 f*******r 的大作中提到】
: common substring的方法是有问题的，比如
: 下面这个input:"abcdecba"
: 以下这个link给了一个正确的方法:
: http://github.com/stevekrenzel/Miscellaneous/blob/9a5d71051b2c3caffdf85a5c96
: 30b85bd177aebc/palindrome/palindrome.py
: 以下是我自己用这个方法写的code，效率是O(N^2)
: //O(N^2)
: void FindLongestPalindrome(char* a)
: {
: if(a==NULL) return;
|
f*********5
发帖数: 576 | 7 1)create a generalized suffix tree for A[0..n] and its reverse string
B[0..n]
###u need to make sure that u can get LCA of two nodes with O(1).
This step is difficult,i think unless u understand it very well,
otherwise it is very difficult to recite..
2) for (i=1;i
find max {LCA(a[i],b[n-1-i]),LCA(a[i+1],b[n-1-i])}
3) the max LCA is just the length of longest parlindrome,
i or i+1 is just the center of the parlindrome
【在 I**A 的大作中提到】
: 有没有什么好办法？
: 我能想到的就是最笨的法子,need O(n^2) time
|
