B*******1
发帖数: 2454 | 1 用suffix tree可以做到o(n),但是现场面试肯定不可能当场写这个suffix tree的。
有另一个解法是lcs(str, reverse(str)），
但是这个方法对于这种string不适合，"abcfghicba"
出来的结果会是abc，是不是这种情况下可以做post-processing,再check得到的这个
substring是不是palindrome啊。
thanks。 |
a********1
发帖数: 750 | |
B*******1
发帖数: 2454 | |
a********1
发帖数: 750 | 4 http://en.wikipedia.org/wiki/Suffix_array
和suffix tree用法几乎一样，但是构造很简单，直接sort pointer就可以了
以前的算法都是用suffix array来构造suffix tree的，后来才发现O(n)的suffix tree
构造算法，，不过那个没可能在面试时候写出来，写出来估计面试官也看不懂
【在 B*******1 的大作中提到】
: 可否说具体点，万分感谢。
|
d*******d
发帖数: 2050 | 5 suffix array/ suffix tree都只能找到lcs,
但是没有解决他的问题.
tree
【在 a********1 的大作中提到】
: http://en.wikipedia.org/wiki/Suffix_array
: 和suffix tree用法几乎一样，但是构造很简单，直接sort pointer就可以了
: 以前的算法都是用suffix array来构造suffix tree的，后来才发现O(n)的suffix tree
: 构造算法，，不过那个没可能在面试时候写出来，写出来估计面试官也看不懂
|
a********1
发帖数: 750 | 6 suffix array可以保存suffix的index
这样check palindrome可以在search的时候check
而不用找完再check
【在 d*******d 的大作中提到】
: suffix array/ suffix tree都只能找到lcs,
: 但是没有解决他的问题.
:
: tree
|
g*****i
发帖数: 2162 | 7 suffix array的lcp 怎么在nlogn算?有code看看吗?
tree
【在 a********1 的大作中提到】
: http://en.wikipedia.org/wiki/Suffix_array
: 和suffix tree用法几乎一样，但是构造很简单，直接sort pointer就可以了
: 以前的算法都是用suffix array来构造suffix tree的，后来才发现O(n)的suffix tree
: 构造算法，，不过那个没可能在面试时候写出来，写出来估计面试官也看不懂
|
r*******g
发帖数: 1335 | 8 Hi
能否详细说说suffix tree怎么做，如果像你们讨论的那样suffix tree很难O(n)构造出
来，那这个题的复杂度究竟是多少呢？我能想到的就是构造两个suffix tree混在一起
，然后再找LCA。
你这里的lcs是什么意思？
谢谢了
【在 B*******1 的大作中提到】
: 用suffix tree可以做到o(n),但是现场面试肯定不可能当场写这个suffix tree的。
: 有另一个解法是lcs(str, reverse(str)），
: 但是这个方法对于这种string不适合，"abcfghicba"
: 出来的结果会是abc，是不是这种情况下可以做post-processing,再check得到的这个
: substring是不是palindrome啊。
: thanks。
|
d*******d
发帖数: 2050 | 9 恩,这个倒是可以做得到.
【在 a********1 的大作中提到】
: suffix array可以保存suffix的index
: 这样check palindrome可以在search的时候check
: 而不用找完再check
|
B*******1
发帖数: 2454 | 10 用suffix array的话，需要建立string 和reverse string的混合的suffix array，还
是只需要建立一个string的suffix array,还是没有弄懂整个用suffix array怎么做，
请指教。
【在 a********1 的大作中提到】
: suffix array可以保存suffix的index
: 这样check palindrome可以在search的时候check
: 而不用找完再check
|
d*******d
发帖数: 2050 | 11 建立混合的, 一起sort.
然后,走一遍,只看来自不同array的相邻两个,看的时候再check一下index看是不是真的
是.
【在 B*******1 的大作中提到】
: 用suffix array的话，需要建立string 和reverse string的混合的suffix array，还
: 是只需要建立一个string的suffix array,还是没有弄懂整个用suffix array怎么做，
: 请指教。
|
B*******1
发帖数: 2454 | 12 Thanks, 我也是这么想的，但是觉得这么做还不如用lcs(str,reverse(str)),dp的时候
每次update maximum length的时候check check是不是palindrome. |
f*********i
发帖数: 197 | 13 楼主,如果你觉得lcs(str,reverse(str)),dp是一个好方法,那么也就是说,你觉得O(n2)
是一个可以接受的解
请看看我提供的解法,这个也是O(n2)时间的
for(every character in string){
1) in aba case:
keep testing two points on its both sides to see if they are the
same
2) in abba case:
Same approach but in abba format
} |
