Verifying and enumerating parameterized border arrays

DOI10.1016/J.TCS.2011.09.008zbMATH Open1228.68067OpenAlexW2036743346MaRDI QIDQ650937FDOQ650937

Hideo Bannai, Shunsuke Inenaga, Tomohiro I, Masayuki Takeda

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.008

Recommendations

• Counting Parameterized Border Arrays for a Binary Alphabet
• Verifying a parameterized border array in \(O(n ^{1.5})\) time
• scientific article; zbMATH DE number 1874382
• The structural border array
• Border Array for Structural Strings

zbMATH Keywords

string matchingenumeration algorithmsreverse engineeringparameterized pattern matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Algorithms on strings (68W32)

Cites Work

• Efficient string matching
• A fast string searching algorithm
• Suffix Arrays: A New Method for On-Line String Searches
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• The smallest automaton recognizing the subwords of a text
• On-line construction of suffix trees
• Parameterized pattern matching: Algorithms and applications
• An on-line string superprimitivity test
• REVERSE ENGINEERING PREFIX TABLES
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Efficient parameterized string matching
• Alphabet dependence in parameterized matching
• Generalization of a suffix tree for RNA structural pattern matching
• Verifying a Parameterized Border Array in O(n 1.5) Time
• Counting Parameterized Border Arrays for a Binary Alphabet
• Lightweight parameterized suffix array construction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiple matching of parameterized patterns
• Parameterized matching with mismatches
• Computing longest previous factor in linear time and applications
• Words over an ordered alphabet and suffix permutations
• Inferring strings from suffix trees and links on a binary alphabet
• Border array on bounded alphabet
• Cover Array String Reconstruction
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2003
• Counting suffix arrays and strings
• Searching subsequences
• Counting distinct strings
• Validating the Knuth-Morris-Pratt Failure Function, Fast and Online
• Periodicity and repetitions in parameterized strings
• Algorithms – ESA 2004
• Reversing Longest Previous Factor Tables is Hard
• Combinatorial Pattern Matching

Cited In (15)

• Universal reconstruction of a string
• String inference from longest-common-prefix array
• Title not available (Why is that?)
• Combinatorics on partial word borders
• Universal Reconstruction of a String
• On suffix tree detection
• Efficient validation and construction of border arrays and validation of string matching automata
• Border array on bounded alphabet
• Border Array for Structural Strings
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Recognizing union-find trees is NP-complete
• A brief history of parameterized matching problems
• Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info
• A suffix tree or not a suffix tree?
• On suffix tree detection

This page was built for publication: Verifying and enumerating parameterized border arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650937)