Jewels of Stringology

DOI10.1142/4838zbMATH Open1078.68151OpenAlexW642038236MaRDI QIDQ4451072FDOQ4451072

Maxime Crochemore, Wojciech Rytter

Publication date: 23 February 2004

Full work available at URL: https://doi.org/10.1142/4838

zbMATH Keywords

pattern matchingtext algorithms

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Analysis of algorithms (68W40) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Combinatorics on words (68R15) Parallel algorithms in computer science (68W10) Computing methodologies for text processing; mathematical typography (68U15)

Cited In (only showing first 100 items - show all)

• Efficient seed computation revisited
• Tree Template Matching in Ranked Ordered Trees by Pushdown Automata
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Watson-Crick Conjugate and Commutative Words
• New simple efficient algorithms computing powers and runs in strings
• Optimal prefix and suffix queries on texts
• Efficient Seeds Computation Revisited
• Universal reconstruction of a string
• Disjunctivity and other properties of sets of pseudo-bordered words
• Title not available (Why is that?)
• The greedy approach to dictionary-based static text compression on a distributed system
• Compressed string-matching in standard Sturmian words
• Multiple pattern matching: a Markov chain approach
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• On del-robust primitive words
• The structure of subword graphs and suffix trees of Fibonacci words
• A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms
• Title not available (Why is that?)
• An extension of the Lyndon-Schützenberger result to pseudoperiodic words
• Spaces, Trees, and Colors
• Relational codes of words
• Unbordered Pictures: Properties and Construction
• Universal Reconstruction of a String
• Asymptotic behaviour of the maximal number of squares in standard Sturmian words
• A fast algorithm for finding the positions of all squares in a run-length encoded string
• Extracting powers and periods in a word from its runs structure
• Simple real-time constant-space string matching
• A linear time algorithm for consecutive permutation pattern matching
• Distinct squares in run-length encoded strings
• Locally compressed suffix arrays
• Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
• Compatibility relations on codes and free monoids
• Fast algorithms for abelian periods in words and greatest common divisor queries
• On regular tree languages and deterministic pushdown automata
• Repetitions in strings: algorithms and combinatorics
• FRIEZES, STRINGS AND CLUSTER VARIABLES
• Tree template matching in ranked ordered trees by pushdown automata
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm
• Forbidden traces and forbidden subtraces
• Asynchronous trace-matching automata
• Time-Optimal Top-$k$ Document Retrieval
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Linear-time construction of two-dimensional suffix trees
• Computing the longest previous factor
• Minimal forbidden subwords
• On-line construction of compact directed acyclic word graphs
• A Linear-Time Algorithm for Seeds Computation
• BLIM: A new bit-parallel pattern matching algorithm overcoming computer word size limitation
• Constructing Words with High Distinct Square Densities
• Sets of Pictures Avoiding Overlaps
• Polynomial-Time Approximation Algorithms for Weighted LCS Problem
• Non-expandable non-overlapping sets of pictures
• An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words
• Unbordered partial words
• Fast algorithm for partial covers in words
• Computing the number of cubic runs in standard Sturmian words
• Simple tree pattern matching for trees in the prefix bar notation
• Indexing factors with gaps
• Scalability and communication in parallel low-complexity lossless compression
• USEFULNESS OF DIRECTED ACYCLIC SUBWORD GRAPHS IN PROBLEMS RELATED TO STANDARD STURMIAN WORDS
• Order-preserving matching
• Distance measures for biological sequences: some recent approaches
• Freeness of partial words
• Equations on partial words
• The number of runs in a string
• Languages with mismatches
• On the maximum number of cubic subwords in a word
• Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform
• A Filtering Technique for All Pairs Approximate Parameterized String Matching
• Simple Real-Time Constant-Space String Matching
• Sturmian and Episturmian Words
• An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence
• Efficient algorithms for shortest partial seeds in words
• Functional programs as compressed data
• Computing the Antiperiod(s) of a String
• Title not available (Why is that?)
• Palindromic decompositions with gaps and errors
• Indexing Circular Patterns
• Efficient dynamic dictionary matching with DAWGs and AC-automata
• Block trees
• Bijective linear time coding and decoding for \(k\)-trees
• Density of distinct squares in non-primitive words
• General suffix automaton construction algorithm and space bounds
• Efficient Computation of 2-Covers of a String.
• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• String Periods in the Order-Preserving Model
• Ternary directed acyclic word graphs
• On modification of Boyer-Moore-Horspool's algorithm for tree pattern matching in linearised trees
• A space efficient direct access data structure
• Automata for solid codes
• An efficient variable-to-fixed length encoding using multiplexed parse trees
• Title not available (Why is that?)
• Finding the cyclic covers of a string
• Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression
• Efficient counting of square substrings in a tree
• On trace inclusion optimization problems
• Maximal and minimal representations of gapped and non-gapped motifs of a string
• Parsing with a finite dictionary
• The wide window string matching algorithm

   Recommendations

• Title not available (Why is that?) 👍 👎
• Algorithms on Strings, Trees and Sequences 👍 👎
• Algorithms on Strings 👍 👎
• 125 Problems in Text Algorithms 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Jewels of Stringology

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