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
Y1 - 2018
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 - https://www.scopus.com/pages/publications/85048260772
UR - https://www.scopus.com/pages/publications/85048260772#tab=citedBy
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 - 23:1-23:16
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 -