The structural border array

DOI10.1016/j.jda.2013.07.003zbMath1334.68311OpenAlexW2067305903MaRDI QIDQ396695

Richard Beal, Donald A. Adjeroh

Publication date: 13 August 2014

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

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

zbMATH Keywords

run-length encodingRNAborderp-borderp-matchp-stringparameterized borderparameterized matchingparameterized stringRLEs-borders-matchs-stringstructural borderstructural matchingstructural string

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Data structures (68P05) Algorithms on strings (68W32)

Related Items

Compressed parameterized pattern matching, Combinatorics on partial word borders, A prefix array for parameterized strings, A brief history of parameterized matching problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized longest previous factor
• Multiple matching of parameterized patterns
• Parameterized searching with mismatches for run-length encoded strings
• Efficient parameterized string matching
• Parameterized matching with mismatches
• Alphabet dependence in parameterized matching
• Compressed matching in dictionaries
• Approximate string matching on Ziv--Lempel compressed text
• Generalization of a suffix tree for RNA structural pattern matching
• \(p\)-suffix sorting as arithmetic coding
• On-line construction of parameterized suffix trees for large alphabets
• Border Array for Structural Strings
• p-Suffix Sorting as Arithmetic Coding
• Verifying a Parameterized Border Array in O(n 1.5) Time
• 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