an algorithm - suffix tree

Question

Given a generalized suffix tree of 2 strings : st1 and st2.

Need to find an algorithm that marks every node V in 1 (and/or 2) if there is a leaf in the sub-tree that goes out of V that represents suffix of st1 (and/ or st2 respectively).

my guess is that we need to use the fact that the last letter of every suffix of st1 is $ and the last letter of every suffix st2 could be #. but it seems to me inefficient to scan tree from bottom to top.

any ideas how to approach it?

for example: I have two strings: st1=abab , st2=aab. in the picture I have made the generalized suffix tree with the marks. so from node with the letter a I have a leaf from his sub tree that represents suffix of st1 so I marked it 1, and I have a leaf from his sub tree that represents suffix of st2 so I marked it 2 as well.

enter image description here

is this http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english what you want? — Andrei Bozantan, Jun 10 '14 at 07:39
no. just because it's about suffix tree, it doesn't mean it's the same question. — Ohad, Jun 10 '14 at 07:48
If you want to mark every node, then you will have to visit every node once. So bottom-top full scan is not such a bad approach. (A given node is marked 1 if any of its children is marked 1). — Kicsi, Jun 10 '14 at 08:25
but how do u scan a tree from bottom to top ? casuse bfs and dfs are from top to bottom... — Ohad, Jun 10 '14 at 08:54

score 0 · Accepted Answer · answered Jun 10 '14 at 09:04

0

When you do DFS, you can mark parent node (after visiting children) with flag for '1' and/or '2', depending if you have end mark for st1/st2 or child is already marked as sufix for st1/st2.

This takes advantage of fact that if any of children contains sufix for st1, then parent also has to contain sufix of st1.

answered Jun 10 '14 at 09:04

MBO

30,379
5
50
52

yes I agree with your idea.. but how to you recognize if you already visited the children of a node ? – Ohad Jun 10 '14 at 09:34
1

It's tree, so if you do proper DFS, then you will always visit all nodes in tree, you don't even have to mark nodes you visit (because there is only 1 way to each node). The only thing you need to take into account is to visit nodes in postorder ordering, so you mark children with flags and then you can check flags or EndOfString marks from "visited" parent. – MBO Jun 10 '14 at 09:57
so what will be the complexity ? O(V) ? If V is the nodes. – Ohad Jun 10 '14 at 10:38

an algorithm - suffix tree

1 Answers1