i****h
发帖数: 321 | 1 如果要O(n1+n2)得到，是不是只有suffix tree的方法啊？谢谢。 | B*****t
发帖数: 335 | 2 suffix array
【在 i****h 的大作中提到】
: 如果要O(n1+n2)得到，是不是只有suffix tree的方法啊？谢谢。
| i****h
发帖数: 321 | 3 我只知道suffix array可以用来计算longest common prefix。。。
能给个link吗？谢谢。
【在 B*****t 的大作中提到】
: suffix array
| i****h
发帖数: 321 | | m******9
发帖数: 968 | 5 wiki上面有一些解释,http://en.wikipedia.org/wiki/Longest_common_substring_problem
不过,我觉得面试的时候还是直接用dp做吧, 代码容易写一些.
难道你真的现场写suffix tree吗? | i****h
发帖数: 321 | 6 我就是想知道有没有比O(mn)更好，又能直接写的算法。
因为看到careercup上面最长对称子序列的题，在一群聒噪的阿三中，小尾羊很淡定的
说了一句，
reverse then O(mn)。。。
【在 m******9 的大作中提到】
: wiki上面有一些解释,http://en.wikipedia.org/wiki/Longest_common_substring_problem
: 不过,我觉得面试的时候还是直接用dp做吧, 代码容易写一些.
: 难道你真的现场写suffix tree吗?
| m******9
发帖数: 968 | 7 他说的方法挺好的
longest palindrome, 就可以用string 和 reverseed string, 然后DP找LCS, 现场
coding也比较方便.
更好的就是你提到的suffix tree |
|
