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
|
|
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
|
|
17 |
Optimal Computation of Avoided Words ...
|
|
|
|
Abstract:
The deviation of the observed frequency of a word $w$ from its expected frequency in a given sequence $x$ is used to determine whether or not the word is avoided. This concept is particularly useful in DNA linguistic analysis. The value of the standard deviation of $w$, denoted by $std(w)$, effectively characterises the extent of a word by its edge contrast in the context in which it occurs. A word $w$ of length $k>2$ is a $ρ$-avoided word in $x$ if $std(w) \leq ρ$, for a given threshold $ρ< 0$. Notice that such a word may be completely absent from $x$. Hence computing all such words na\"ıvely can be a very time-consuming procedure, in particular for large $k$. In this article, we propose an $O(n)$-time and $O(n)$-space algorithm to compute all $ρ$-avoided words of length $k$ in a given sequence $x$ of length $n$ over a fixed-sized alphabet. We also present a time-optimal $O(σn)$-time and $O(σn)$-space algorithm to compute all $ρ$-avoided words (of any length) in a sequence of length $n$ over an ...
|
|
Keyword:
Data Structures and Algorithms cs.DS; FOS Computer and information sciences
|
|
URL: https://dx.doi.org/10.48550/arxiv.1604.08760 https://arxiv.org/abs/1604.08760
|
|
BASE
|
|
Hide 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
|
|
|
|