Výsledky vyhledávání - "Prefix normal form"

On prefix normal words and prefix normal forms

Autor: Joe Sawada, Péter Burcsi, Zsuzsanna Lipták, Gabriele Fici, Frank Ruskey

Publikováno v: Theoretical Computer Science. 659:1-13

A $1$-prefix normal word is a binary word with the property that no factor has more $1$s than the prefix of the same length; a $0$-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b63a01fdf2a63583d6e0de86ed551afc
https://doi.org/10.1016/j.tcs.2016.10.015

Zobrazit plný text záznamu

Binary jumbled string matching for highly run-length compressible texts

Autor: Gabriele Fici, Zsuzsanna Lipták, Golnaz Badkobeh, Steve Kroon

Publikováno v: Information Processing Letters. 113:604-608

The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous sol

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::224cd8421949039ed1349eaab3331fe6
https://doi.org/10.1016/j.ipl.2013.05.007

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Report

Weighted Prefix Normal Words: Mind the Gap

Autor: Eikmeier, Yannik, Fleischmann, Pamela, Kulczynski, Mitja, Nowotka, Dirk

A prefix normal word is a binary word whose prefixes contain at least as many 1s as any of its factors of the same length. Introduced by Fici and Lipt\'ak in 2011 the notion of prefix normality is so far only defined for words over the binary alphabe

Externí odkaz: http://arxiv.org/abs/2005.09281