15 citations · 40 across the 14 of their papers we have counts for
14 papers
Practical KMP/BM Style Pattern-Matching on Indeterminate Strings
Hossein Dehghani, Neerja Mhaskar, W. F. Smyth
In this paper we describe two simple, fast, space-efficient algorithms for finding all matches of an indeterminate pattern in an indeterminate string , w…
A New Approach to Regular & Indeterminate Strings
Felipe A. Louza, Neerja Mhaskar, W. F. Smyth
In this paper we propose a new, more appropriate definition of regular and indeterminate strings. A regular string is one that is "isomorphic" to a string whose entries all consist…
Palindromes in starlike trees
Amy Glen, Jamie Simpson, W. F. Smyth
In this note, we obtain an upper bound on the maximum number of distinct non-empty palindromes in starlike trees. This bound implies, in particular, that there are at most dis…
On the Parikh-de-Bruijn grid
Péter Burcsi, Zsuzsanna Lipták, W. F. Smyth
We introduce the Parikh-de-Bruijn grid, a graph whose vertices are fixed-order Parikh vectors, and whose edges are given by a simple shift operation. This graph gives structural in…
Lyndon Array Construction during Burrows-Wheeler Inversion
Felipe A. Louza, W. F. Smyth, Giovanni Manzini +1
In this paper we present an algorithm to compute the Lyndon array of a string of length as a byproduct of the inversion of the Burrows-Wheeler transform of . Our algorit…
More properties of the Fibonacci word on an infinite alphabet
Amy Glen, Jamie Simpson, W. F. Smyth
Recently the Fibonacci word on an infinite alphabet was introduced by [Zhang et al., Electronic J. Combinatorics 24-2 (2017) #P2.52] as a fixed point of the morphism $ϕ: (2i) \…
Counting Lyndon factors
Amy Glen, Jamie Simpson, W. F. Smyth
In this paper, we determine the maximum number of distinct Lyndon factors that a word of length can contain. We also derive formulas for the expected total number of Lyndon fac…
Algorithms to Compute the Lyndon Array
Frantisek Franek, A. S. M. Sohidull Islam, M. Sohel Rahman +1
We first describe three algorithms for computing the Lyndon array that have been suggested in the literature, but for which no structured exposition has been given. Two of these al…
A Note on Easy and Efficient Computation of Full Abelian Periods of a Word
Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre +2
Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if…
String Comparison in -Order: New Lexicographic Properties & On-line Applications
Ali Alatabbi, Jacqueline W. Daykin, M. Sohel Rahman +1
-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), which are themselves generalizations of Lyndon words. -order has recently been p…
Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables
Ali Alatabbi, A. S. Sohidull Islam, M. Sohel Rahman +2
A \itbf{cover} of a string is a proper substring of such that can be constructed from possibly overlapping instances of . A recent paper \cite{FIKPPST1…
Inferring an Indeterminate String from a Prefix Graph
Ali Alatabbi, M. Sohel Rahman, W. F. Smyth
An \itbf{indeterminate string} (or, more simply, just a \itbf{string}) $\s{x} = \s{x}[1..n]$ on an alphabet is a sequence of nonempty subsets of . We say that $\s{x}[i_1]$ a…
Computing Covers Using Prefix Tables
Ali Alatabbi, M. Sohel Rahman, W. F. Smyth
An \emph{indeterminate string} on an alphabet is a sequence of nonempty subsets of ; is said to be \emph{regular} if every subset is of size one. A proper…
Indeterminate Strings, Prefix Arrays & Undirected Graphs
Manolis Christodoulakis, P. J. Ryan, W. F. Smyth +1
An integer array y = y[1..n] is said to be feasible if and only if y[1] = n and, for every i \in 2..n, i \le i+y[i] \le n+1. A string is said to be indeterminate if and only if at…