g******0
发帖数: 221 | 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 | g*****k
发帖数: 623 | 2 only one step to reach the leaf.
for suffix tree, the internal node provide random access, so it is constant
time to traverse the subtree along the edge "e" in this case.
search
【在 g******0 的大作中提到】
: 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
: |
| l*****a
发帖数: 559 | 3 呵呵，if you know suffix tree can be built in O(n) time, you should also
know that s2 can be found by traversing all children of the root node.
suffix
search
【在 g******0 的大作中提到】
: 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
: |
|
|
