![]() |
COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. | ![]() |
University of Cambridge > Talks.cam > Computer Laboratory Wednesday Seminars > Semi-local string comparison
![]() Semi-local string comparisonAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Stephen Clark. The computation of a longest common subsequence (LCS) between two strings is a classical algorithmic problem. Some applications require a generalisation of this problem, which we call semi-local LCS . It asks for the LCS between a string and all substrings of another string, and/or the LCS between all prefixes of one string and all suffixes of another. Apart from an important role that this generalised problem plays in string algorithms, it turns out to have surprising connections with semigroup algebra, computational geometry, planar graph algorithms, comparison networks, as well as practical applications in computational biology. The talk will present an efficient solution for the semi-local LCS problem, and will survey some related results and applications. Among those are dynamic LCS support; fast clique computation in special graphs; fast comparison of compressed strings; parallel string algorithms. This talk is part of the Computer Laboratory Wednesday Seminars series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsNUDT Visitors Seminars BRC Seminar Series Developmental Neurobiology Seminar Series Isaac Newton Institute Seminar Series Cambridge University Global Health Society Type the title of a new list hereOther talksMigration in Science Short-Selling Restrictions and Returns: a Natural Experiment Climate Change Uncertainty, Adaptation, and Growth NatHistFest: the 99th Conversazione and exhibition on the wonders of the natural world. Cancer and Metbolism 2018 Internal Displacement in Cyprus and childhood: The view from genetic social psychology Immigration and Freedom Constructing the virtual fundamental cycle TBC Discovering regulators of insulin output with flies and human islets: implications for diabetes and pancreas cancer The Gopakumar-Vafa conjecture for symplectic manifolds Intelligence and the frontal lobes |