Talk:Suffix tree: Difference between revisions
Content added Content deleted
Line 47: | Line 47: | ||
::::::: 4. from node 3, edge '$' pointing to a leaf node, and 'a$' pointing to a leaf node. |
::::::: 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.) |
::::::: 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.) |
||
:::::::: Ok, this helped greatly, because it conveyed to me the definition of "edge" (or an important part of that definition). A study of the patricia tree link from the wikipedia page also helped. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 13:05, 27 May 2013 (UTC) |
|||
== definition (take 2) == |
== definition (take 2) == |