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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可否说具体点,万分感谢。
|
d*******d 发帖数: 2050 | 5 suffix array/ suffix tree都只能找到lcs,
但是没有解决他的问题.
tree
【在 a********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : suffix array/ suffix tree都只能找到lcs, : 但是没有解决他的问题. : : tree
|
g*****i 发帖数: 2162 | 7 suffix array的lcp 怎么在nlogn算?有code看看吗?
tree
【在 a********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : suffix array可以保存suffix的index : 这样check palindrome可以在search的时候check : 而不用找完再check
|
d*******d 发帖数: 2050 | 11 建立混合的, 一起sort.
然后,走一遍,只看来自不同array的相邻两个,看的时候再check一下index看是不是真的
是.
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用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
} |