Locating maximal approximate runs in a string (Q2410363)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Locating maximal approximate runs in a string |
scientific article |
Statements
Locating maximal approximate runs in a string (English)
0 references
17 October 2017
0 references
The authors show how, given a string \(T\) of \(n\) characters and a bound \(k\), we can find in \(O (n k^2 \log k + \mathrm{occ})\) time all the \(\mathrm{occ}\) triples \((i, j, p)\) such that, first, the substring \(T [i, j]\) is within Hamming distance \(k\) of a string with period \(p \leq (j-i+1)/2\) and, second, \(T [i, j]\) is not contained within a longer substring also within Hamming distance \(k\) of a string with period \(p\). Their algorithm reuses several ideas from Kolpakov and Kucherov's \(O (n k \log k + \mathrm{occ})\)-time algorithm [\textit{R. Kolpakov} and \textit{G. Kucherov}, Theor. Comput. Sci. 303, No. 1, 135--156 (2003; Zbl 1051.68119)] for the variant of the problem in which the restriction on \(T [i, j]\) is that \(T [i..j - p]\) and \(T [i + p..j]\) are at Hamming distance at most \(k\) from each other.
0 references
algorithms on strings
0 references
pattern matching
0 references
repetitions
0 references
tandem repeats
0 references
runs
0 references
Hamming distance
0 references