Zobrazeno 1 - 10
of 169
pro vyhledávání: '"SHINOHARA, Ayumi"'
This paper is concerned with subsequences that consist of limited numbers of segments. We call a subsequence {$f$-segmental} if it is composed of $f$ factors. More precisely, any string of the form $u_1 \dots u_f$ is an $f$-segmental subsequence of a
Externí odkaz:
http://arxiv.org/abs/2407.19796
Lyndon words are extensively studied in combinatorics on words -- they play a crucial role on upper bounding the number of runs a word can have [Bannai+, SIAM J. Comput.'17]. We can determine Lyndon words, factorize a word into Lyndon words in lexico
Externí odkaz:
http://arxiv.org/abs/2403.02636
Autor:
Iseri, Kento, I, Tomohiro, Hendrian, Diptarama, Köppl, Dominik, Yoshinaka, Ryo, Shinohara, Ayumi
A parameterized string (p-string) is a string over an alphabet $(\Sigma_{s} \cup \Sigma_{p})$, where $\Sigma_{s}$ and $\Sigma_{p}$ are disjoint alphabets for static symbols (s-symbols) and for parameter symbols (p-symbols), respectively. Two p-string
Externí odkaz:
http://arxiv.org/abs/2308.05977
The parameterized matching problem is a variant of string matching, which is to search for all parameterized occurrences of a pattern $P$ in a text $T$. In considering matching algorithms, the combinatorial natures of strings, especially periodicity,
Externí odkaz:
http://arxiv.org/abs/2306.10714
Position heaps are index structures of text strings used for the string matching problem. They are rooted trees whose edges and nodes are labeled and numbered, respectively. This paper is concerned with variants of the inverse problem of position hea
Externí odkaz:
http://arxiv.org/abs/2209.12405
Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characters and the other to be the alphabet of parameter characters. Two param
Externí odkaz:
http://arxiv.org/abs/2206.15100
Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation $\approx$ is called a substring consistent equivalence relation (SCER), if for two strings $X$
Externí odkaz:
http://arxiv.org/abs/2202.13284
One of the most well-known variants of the Burrows-Wheeler transform (BWT) [Burrows and Wheeler, 1994] is the bijective BWT (BBWT) [Gil and Scott, arXiv 2012], which applies the extended BWT (EBWT) [Mantaci et al., TCS 2007] to the multiset of Lyndon
Externí odkaz:
http://arxiv.org/abs/2004.12590
We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string $T$ has been compressed as a context-free grammar $G$ in Chomsky normal form satisfying $L(G) = \{T\}$. Such a grammar
Externí odkaz:
http://arxiv.org/abs/2003.08097
Given a text $T$ of length $n$ and a pattern $P$ of length $m$, the string matching problem is a task to find all occurrences of $P$ in $T$. In this study, we propose an algorithm that solves this problem in $O((n + m)q)$ time considering the distanc
Externí odkaz:
http://arxiv.org/abs/2002.08004