aa瞎扯淡 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

aa瞎扯淡

aa瞎扯淡# Money - 海外理财

B*12013-01-17 08:01

1 楼

用suffix tree可以做到o(n),但是现场面试肯定不可能当场写这个suffix tree的。
有另一个解法是lcs(str, reverse(str)），
但是这个方法对于这种string不适合，"abcfghicba"
出来的结果会是abc，是不是这种情况下可以做post-processing,再check得到的这个
substring是不是palindrome啊。
thanks。

d*n2013-01-17 08:01

2 楼

以前的 logo 挺好，非得换个不伦不类的新的。有这功夫不如多弄点75k开卡bonus出来。

a*12013-01-17 08:01

3 楼

suffix array nlogn

B*12013-01-17 08:01

4 楼

可否说具体点，万分感谢。

a*12013-01-17 08:01

5 楼

http://en.wikipedia.org/wiki/Suffix_array
和suffix tree用法几乎一样，但是构造很简单，直接sort pointer就可以了
以前的算法都是用suffix array来构造suffix tree的，后来才发现O(n)的suffix tree
构造算法，，不过那个没可能在面试时候写出来，写出来估计面试官也看不懂

【在 B*******1 的大作中提到】

: 可否说具体点，万分感谢。

d*d2013-01-17 08:01

6 楼

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*12013-01-17 08:01

7 楼

suffix array可以保存suffix的index
这样check palindrome可以在search的时候check
而不用找完再check

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

: suffix array/ suffix tree都只能找到lcs,
: 但是没有解决他的问题.
:
: tree

g*i2013-01-17 08:01

8 楼

suffix array的lcp 怎么在nlogn算?有code看看吗?

tree

【在 a********1 的大作中提到】

r*g2013-01-17 08:01

9 楼

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*d2013-01-17 08:01

10 楼

恩,这个倒是可以做得到.

【在 a********1 的大作中提到】

: suffix array可以保存suffix的index
: 这样check palindrome可以在search的时候check
: 而不用找完再check

B*12013-01-17 08:01

11 楼

用suffix array的话，需要建立string 和reverse string的混合的suffix array，还
是只需要建立一个string的suffix array,还是没有弄懂整个用suffix array怎么做，
请指教。

【在 a********1 的大作中提到】

: suffix array可以保存suffix的index
: 这样check palindrome可以在search的时候check
: 而不用找完再check

d*d2013-01-17 08:01

12 楼

建立混合的, 一起sort.
然后,走一遍,只看来自不同array的相邻两个,看的时候再check一下index看是不是真的
是.

【在 B*******1 的大作中提到】

: 用suffix array的话，需要建立string 和reverse string的混合的suffix array，还
: 是只需要建立一个string的suffix array,还是没有弄懂整个用suffix array怎么做，
: 请指教。

B*12013-01-17 08:01

13 楼

Thanks, 我也是这么想的，但是觉得这么做还不如用lcs(str,reverse(str)),dp的时候
每次update maximum length的时候check check是不是palindrome.

f*i2013-01-17 08:01

14 楼

楼主,如果你觉得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
}