Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Linear-Time Algorithm for Long LCF with k Mismatches

Uproszczony widok
dc.abstract.enIn the Longest Common Factor with k Mismatches (LCF_k) problem, we are given two strings X and Y of total length n, and we are asked to find a pair of maximal-length factors, one of X and the other of Y, such that their Hamming distance is at most k. Thankachan et al. [Thankachan et al. 2016] show that this problem can be solved in O(n log^k n) time and O(n) space for constant k. We consider the LCF_k(l) problem in which we assume that the sought factors have length at least l. We use difference covers to reduce the LCF_k(l) problem with l=Omega(log^{2k+2}n) to a task involving m=O(n/log^{k+1}n) synchronized factors. The latter can be solved in O(m log^{k+1}m) time, which results in a linear-time algorithm for LCF_k(l) with l=Omega(log^{2k+2}n). In general, our solution to the LCF_k(l) problem for arbitrary l takes O(n + n log^{k+1} n/sqrt{l}) time.
dc.affiliationUniwersytet Warszawski
dc.conference.countryChiny
dc.conference.datefinish2018-07-04
dc.conference.datestart2018-07-02
dc.conference.placeQingdao
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesshortcutCPM
dc.conference.shortcutCPM 2018
dc.conference.weblinkhttp://cpm2018.sdu.edu.cn/
dc.contributor.authorIliopoulos, Costas S.
dc.contributor.authorRadoszewski, Jakub
dc.contributor.authorKociumaka, Tomasz
dc.contributor.authorCrochemore, Maxime
dc.contributor.authorWaleń, Tomasz
dc.contributor.authorRytter, Wojciech
dc.contributor.authorPissis, Solon P.
dc.contributor.authorCharalampopoulos, Panagiotis
dc.date.accessioned2024-01-25T05:11:31Z
dc.date.available2024-01-25T05:11:31Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.identifier.doi10.4230/LIPICS.CPM.2018.23
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111277
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2018/8686/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages23:1--23:16
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enlongest common factor
dc.subject.enlongest common substring
dc.subject.enHamming distance
dc.subject.enheavy-light decomposition
dc.subject.endifference cover
dc.titleLinear-Time Algorithm for Long LCF with k Mismatches
dc.typeJournalArticle
dspace.entity.typePublication