Jewels of Stringology

DOI10.1142/4838zbMath1078.68151OpenAlexW642038236MaRDI QIDQ4451072

Publication date: 23 February 2004

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

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

Related Items

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