问一个很简单的suffix tree问题。请指点。# JobHunting - 待字闺中
g*0
1 楼
Given two strings: s1(length n),s2(length m).
Building the suffix tree of s1 takes O(n) time. To search s2 in the suffix
tree of s1 takes O(m). Why?
For example: s1: abcde, s2: e. The tree is shown below. Shouldn't the search
time be O(n)? 弱问，what did i miss? Maybe I should ask what is data
structure of the children of a node in a suffix tree? many thanks!
|(1:abcde)|leaf
tree:|
|(2:bcde)|leaf
|
|(3:cde)|leaf
|
|(4:de)|leaf
|
|(5:e)|leaf
Building the suffix tree of s1 takes O(n) time. To search s2 in the suffix
tree of s1 takes O(m). Why?
For example: s1: abcde, s2: e. The tree is shown below. Shouldn't the search
time be O(n)? 弱问，what did i miss? Maybe I should ask what is data
structure of the children of a node in a suffix tree? many thanks!
|(1:abcde)|leaf
tree:|
|(2:bcde)|leaf
|
|(3:cde)|leaf
|
|(4:de)|leaf
|
|(5:e)|leaf
