Re:Topics in Advanced Data Structures [pdf]
by htiek on Monday April 29, 2019 @02:30PM
(#19781145)
You can use lowest common ancestor queries in conjunction with suffix trees to solve a lot of interesting string problems. For example, take two indices within a string, find their corresponding suffixes in the suffix tree, and then take their LCA. That gives you an internal node corresponding to the longest string that appears starting at both indices (this is called their "longest common extension.") You can use this as a subroutine in a bunch of genomics applications.
[ Parent
| on HN ]
Re:Topics in Advanced Data Structures [pdf]
by lichtenberger on Monday April 29, 2019 @02:43PM
(#19781296)
Thanks, great use case and I have to say I have to read about genomics... :-)