A prefix array for parameterized strings

DOI10.1016/j.jda.2016.11.002zbMath1359.68329OpenAlexW2552773400MaRDI QIDQ511148

Richard Beal, W. F. Smyth, Donald A. Adjeroh

Publication date: 14 February 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2016.11.002

zbMATH Keywords

p-matchp-stringchpPAcompact parameterized prefix arraycpPAhp-matchhp-stringparameterized longest previous factorparameterized prefix arrayparameterized string with holespLPFpPA

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items

A brief history of parameterized matching problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structural border array
• Efficient algorithms for three variants of the LPF table
• Parameterized longest previous factor
• Indeterminate strings, prefix arrays \& undirected graphs
• Efficient pattern matching for RNA secondary structures
• Multiple matching of parameterized patterns
• Parameterized searching with mismatches for run-length encoded strings
• Efficient parameterized string matching
• Parameterized matching with mismatches
• Fast pattern-matching on indeterminate strings
• Computing longest previous factor in linear time and applications
• Alphabet dependence in parameterized matching
• Generalization of a suffix tree for RNA structural pattern matching
• Variations of the parameterized longest previous factor
• \(p\)-suffix sorting as arithmetic coding
• On-line construction of parameterized suffix trees for large alphabets
• Computing longest previous non-overlapping factors
• Inferring an indeterminate string from a prefix graph
• Generalized function matching
• Prefix Table Construction and Conversion
• New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
• An O(n log n) algorithm for finding all repetitions in a string
• IDENTIFYING RHYTHMS IN MUSICAL TEXTS
• Verifying a Parameterized Border Array in O(n 1.5) Time
• Approximate parameterized matching
• Counting Parameterized Border Arrays for a Binary Alphabet
• Lightweight Parameterized Suffix Array Construction
• Algorithms on Strings, Trees and Sequences
• Faster Suffix Tree Construction with Missing Suffix Links
• A theory of parameterized pattern matching
• Algorithmic Combinatorics on Partial Words
• Algorithms on Strings