hamming_compressed<\/a><\/p>\nGiven a text and a pattern, computing all occurrences of the pattern in the text in one of the fundamental problems of stringology, which has myriads applications in practice (think of searching for a keyword in a long file).<\/p>\n
However, in real life a pattern may never match the text exactly, and one should instead aim to find locations where it is only similar to the text.<\/p>\n
In this course, we will consider one of the possible formulations of this task, which requires computing the Hamming distance (the number of mismatches) between a pattern of length m<\/em> and every m<\/em>-length substring of the text. We will discuss recent advances and open questions related to this famous problem.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"Tatiana Starikovskaya, \u00e9quipe TAlgo, INRIA et d\u00e9partement informatique de l\u2019ENS Paris The slides are here: hamming_compressed Given a text and a pattern, computing all occurrences of the pattern in the text in one of the fundamental problems of stringology, which has myriads applications in practice (think of searching for a keyword in a long file). […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-375","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=\/wp\/v2\/pages\/375","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=375"}],"version-history":[{"count":6,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=\/wp\/v2\/pages\/375\/revisions"}],"predecessor-version":[{"id":405,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=\/wp\/v2\/pages\/375\/revisions\/405"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/confsrentree\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![](\"https:\/\/starikovskaya.github.io\/homepage\/images\/starikovskaya_2.jpg\")
<\/p>\n