Google: 找公共prefix

给一组字符串,找出他们的common prefix

所有字符串的 common prefix? 貌似直接遍歷就好了吧?
O(nL), where L is the largest possible length of strings and n is the size of the set.

所有字符串的 common prefix? 貌似直接遍歷就好了吧?
O(nL), where L is the largest possible length of strings and n is the size of the set.
iveney 发表于 2011-8-24 09:40

    对阿，偶尔google也会出简单题，万一想复杂了跑到suffix tree就不好了

...但是用suffix tree确实只需要O(n+L).

这编程题，是不是如果用suffix tree还得代码实现？

...但是用suffix tree确实只需要O(n+L).
coder 发表于 2011-8-25 05:16

    How come???

还没仔细研究，因为构造的code貌似十分麻烦，我还不会。但构造一个generalized suffix tree 需要O(set of strings的总长度),不是O(n+L)，sorry, where n is the quantity of strings, L is the longest length. 查找不需遍历，我的理解是第一个分叉点以前的就是prefix.
FYI，http://en.wikipedia.org/wiki/Generalised_suffix_tree