Jewels of Stringology

DOI10.1142/4838zbMATH Open1078.68151OpenAlexW642038236MaRDI QIDQ4451072FDOQ4451072

Authors: Maxime Crochemore, Wojciech Rytter 

Publication date: 23 February 2004

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

Recommendations

• scientific article; zbMATH DE number 801745
• Algorithms on Strings, Trees and Sequences
• Algorithms on Strings
• 125 problems in text algorithms. With solutions
• scientific article; zbMATH DE number 828444

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
• Unbordered pictures: properties and construction
• 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
• Sets of pictures avoiding overlaps
• Universal reconstruction of a string
• Universal reconstruction of a string
• Constructing words with high distinct square densities
• Disjunctivity and other properties of sets of pseudo-bordered words
• Polynomial-time approximation algorithms for weighted LCS problem
• 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
• Relational codes of words
• A filtering technique for all pairs approximate parameterized string matching
• Asymptotic behaviour of the maximal number of squares in standard Sturmian words
• Simple real-time constant-space string matching
• Time-optimal top-\(k\) document retrieval
• 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
• Algorithms on Strings
• Usefulness of directed acyclic subword graphs in problems related to standard Sturmian words
• 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
• 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
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Efficient and secure generalized pattern matching via Fast Fourier Transform
• 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
• 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
• Efficient seeds computation revisited
• Scalability and communication in parallel low-complexity lossless compression
• 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
• 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?)
• On new algorithms of mutual transformation of string schemes
• Palindromic decompositions with gaps and errors
• Indexing Circular Patterns
• Efficient dynamic dictionary matching with DAWGs and AC-automata
• Unweighted and weighted hyper-minimization
• 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
• Tuning the Zhu-Takaoka string matching algorithm and experimental results.
• Palindromic decompositions with gaps and errors
• Automata for solid codes
• An efficient variable-to-fixed length encoding using multiplexed parse trees
• Title not available (Why is that?)
• Boosting pattern matching performance via \(k\)-bit filtering
• Arbology: trees and pushdown automata
• Finding the cyclic covers of a string

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)