TY - GEN
T1 - Linear-time algorithm for long LCF with κ mismatches
AU - Charalampopoulos, Panagiotis
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Kociumaka, Tomasz
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Waleń, Tomasz
PY - 2018/5/1
Y1 - 2018/5/1
N2 - In the Longest Common Factor with κ Mismatches (LCFκ) 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 κ. Thankachan et al. [27] show that this problem can be solved in O(n logκ n) time and O(n) space for constant k. We consider the LCFκ (ℓ) problem in which we assume that the sought factors have length at least ℓ. We use difference covers to reduce the LCFκ (ℓ) problem with ℓ = Ω(log2κ+2 n) to a task involving m = O(n/logκ+1 n) synchronized factors. The latter can be solved in O(mlogκ+1 m) time, which results in a linear-time algorithm for LCFκ (ℓ) with ℓ = Ω(log2κ+2 n). In general, our solution to the LCFκ(ℓ) problem for arbitrary ℓ takes O(n + n logκ+1 n/√ℓ) time.
AB - In the Longest Common Factor with κ Mismatches (LCFκ) 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 κ. Thankachan et al. [27] show that this problem can be solved in O(n logκ n) time and O(n) space for constant k. We consider the LCFκ (ℓ) problem in which we assume that the sought factors have length at least ℓ. We use difference covers to reduce the LCFκ (ℓ) problem with ℓ = Ω(log2κ+2 n) to a task involving m = O(n/logκ+1 n) synchronized factors. The latter can be solved in O(mlogκ+1 m) time, which results in a linear-time algorithm for LCFκ (ℓ) with ℓ = Ω(log2κ+2 n). In general, our solution to the LCFκ(ℓ) problem for arbitrary ℓ takes O(n + n logκ+1 n/√ℓ) time.
KW - Difference cover
KW - Hamming distance
KW - Heavy-light decomposition
KW - Longest common factor
KW - Longest common substring
UR - http://www.scopus.com/inward/record.url?scp=85048260772&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048260772&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2018.23
DO - 10.4230/LIPIcs.CPM.2018.23
M3 - Conference contribution
AN - SCOPUS:85048260772
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 231
EP - 2316
BT - 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
A2 - Zhu, Binhai
A2 - Navarro, Gonzalo
A2 - Sankoff, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
Y2 - 2 July 2018 through 4 July 2018
ER -