Anonymous user
Talk:Suffix tree: Difference between revisions
→definition?
(→definition (take 2): damn it I keep writing it wrong) |
|||
Line 40:
:::::: Actually, that banana$ example - enumerating the edges there, combined with a re-read of the definition and realizing that it's not making any O(1) guarantees at the nodes -- I now think that the suffix tree representation of 'aaaaaaa$' winds up enumerating all the edges which start with 'a' at a single node -- helps quite a lot. Thank you. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 14:08, 26 May 2013 (UTC)
::::::: No. It's not "only one edge leading out is allowed", but "only one edge starting with each letter is allowed". For "aaaa$", you have:
::::::: 1. from root node, edge '$' pointing to a leaf node, and edge 'a' pointing to internal node 1;
::::::: 2. from node 1, edge '$' pointing to a leaf node, and 'a' pointing to internal node 2;
::::::: 3. from node 2, edge '$' pointing to a leaf node, and 'a' pointing to internal node 3;
::::::: 4. from node 3, edge '$' pointing to a leaf node, and 'a$' pointing to a leaf node.
::::::: You can just add more nodes like 2 and 3 if you insert more 'a's to the string. String matching works exactly like a trie lookup (actually, it ''is'' exactly a trie lookup, and it really only takes O(1) time to decide which edge to follow at each node ''unless you don't want to'' (one C implementation referrenced by the WP article stores edges in a linked list, but it could easily have used a hash table or a dynamic array.)
== definition (take 2) ==
| |||