| 1 |
Constructing Strings Avoiding Forbidden Substrings
|
|
|
|
In: CPM 2021 - 32nd Annual Symposium on Combinatorial Pattern Matching ; https://hal.inria.fr/hal-03395386 ; CPM 2021 - 32nd Annual Symposium on Combinatorial Pattern Matching, Jul 2021, Wroclaw, Poland. pp.1-18 (2021)
|
|
BASE
|
|
Show details
|
|
|
| 6 |
Bidirectional String Anchors: A New String Sampling Mechanism ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 7 |
Unary Words Have the Smallest Levenshtein k-Neighbourhoods
|
|
|
|
Abstract:
The edit distance (a.k.a. the Levenshtein distance) between two words is defined as the minimum number of insertions, deletions or substitutions of letters needed to transform one word into another. The Levenshtein k-neighbourhood of a word w is the set of words that are at edit distance at most k from w. This is perhaps the most important concept underlying BLAST, a widely-used tool for comparing biological sequences. A natural combinatorial question is to ask for upper and lower bounds on the size of this set. The answer to this question has important algorithmic implications as well. Myers notes that "such bounds would give a tighter characterisation of the running time of the algorithm" behind BLAST. We show that the size of the Levenshtein k-neighbourhood of any word of length n over an arbitrary alphabet is not smaller than the size of the Levenshtein k-neighbourhood of a unary word of length n, thus providing a tight lower bound on the size of the Levenshtein k-neighbourhood. We remark that this result was posed as a conjecture by Dufresne at WCTA 2019.
|
|
Keyword:
combinatorics on words; Data processing Computer science; edit distance; Levenshtein distance
|
|
URN:
urn:nbn:de:0030-drops-121359
|
|
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12135/
https://doi.org/10.4230/LIPIcs.CPM.2020.10
|
|
BASE
|
|
Hide details
|
|
|
| 9 |
Longest Unbordered Factor in Quasilinear Time
|
|
Kociumaka, Tomasz; Kundu, Ritu; Mohamed, Manal. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. : LIPIcs - Leibniz International Proceedings in Informatics. 29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018
|
|
BASE
|
|
Show details
|
|
|
| 10 |
Longest Common Prefixes with $k$-Errors and Applications ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 16 |
Efficient Index for Weighted Sequences
|
|
Barton, Carl; Kociumaka, Tomasz; Pissis, Solon P.. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. : LIPIcs - Leibniz International Proceedings in Informatics. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2016
|
|
BASE
|
|
Show details
|
|
|
| 18 |
Linear-time computation of minimal absent words using suffix array
|
|
|
|
BASE
|
|
Show details
|
|
|
| 19 |
Order-Preserving Suffix Trees and Their Algorithmic Applications ...
|
|
|
|
BASE
|
|
Show details
|
|
|
|
|
