Algorithms on Strings
From MaRDI portal
Publication:5444160
DOI10.1017/CBO9780511546853zbMath1137.68060MaRDI QIDQ5444160
Christophe Hancart, Maxime Crochemore, Thierry Lecroq
Publication date: 22 February 2008
Searching and sorting (68P10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Nonnumerical algorithms (68W05) Computing methodologies for text processing; mathematical typography (68U15)
Related Items
Invariants for time-series constraints, New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings, On-line string matching in highly similar DNA sequences, Faster average case low memory semi-external construction of the Burrows-Wheeler transform, Lyndon + Christoffel = digitally convex, Computing minimal and maximal suffixes of a substring, From Nerode's congruence to suffix automata with mismatches, On left and right seeds of a string, Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations, Palindromic decompositions with gaps and errors, Longest previous overlapping factor array, All-pairs suffix/prefix in optimal time using Aho-Corasick space, Two strings at Hamming distance 1 cannot be both quasiperiodic, Covering problems for partial words and for indeterminate strings, Locating maximal approximate runs in a string, Border correlations, lattices, and the subgraph component polynomial, Computing primitively-rooted squares and runs in partial words, Validating the Knuth-Morris-Pratt failure function, fast and online, String powers in trees, Searching of gapped repeats and subrepetitions in a word, Extracting powers and periods in a word from its runs structure, Efficient seed computation revisited, Enhanced string covering, Linear computation of unbordered conjugate on unordered alphabet, A note on a simple computation of the maximal suffix of a string, On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case, Checking whether a word is Hamming-isometric in linear time, Combinatorics on partial word borders, Efficient algorithms for three variants of the LPF table, Computing maximal-exponent factors in an overlap-free word, Negative selection algorithms on strings with efficient training and linear-time classification, Computing longest previous non-overlapping factors, Period recovery of strings over the Hamming and edit distances, Efficient algorithms for shortest partial seeds in words, Deriving generic bounds for time-series constraints based on regular expressions characteristics, Using minimal absent words to build phylogeny, Note on the greedy parsing optimality for dictionary-based text compression, Revisiting the parameterized complexity of maximum-duo preservation string mapping, Dynamic and internal longest common substring, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Hide and seek with repetitions, Fast computation of a longest increasing subsequence and application, Prefix partitioned Gray codes for particular cross-bifix-free sets, An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints, Asynchronous trace-matching automata, Experimental evaluation of algorithms for computing quasiperiods, Computing a longest common almost-increasing subsequence of two sequences, Using static suffix array in dynamic application: case of text compression by longest first substitution, Dynamic edit distance table under a general weighted cost function, On a lemma of Crochemore and Rytter, A note on the longest common compatible prefix problem for partial words, Fast algorithm for partial covers in words, Indeterminate strings, prefix arrays \& undirected graphs, New simple efficient algorithms computing powers and runs in strings, Automata for solid codes, Linear-time version of Holub's algorithm for morphic imprimitivity testing, On-line weighted pattern matching, Binary block order Rouen transform, Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings, Linear-time computation of prefix table for weighted strings {\&} applications, Two fast constructions of compact representations of binary words with given set of periods, Efficient computation of maximal anti-exponent in palindrome-free strings, A prefix array for parameterized strings, Quantum pattern matching fast on average, Cross-bifix-free sets in two dimensions, On trace inclusion optimization problems, On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties, Efficient algorithms for the longest common subsequence in \(k\)-length substrings, Pattern matching and consensus problems on weighted sequences and profiles, Disjunctivity and other properties of sets of pseudo-bordered words, Computing longest previous factor in linear time and applications, Computing the longest previous factor, Special factors and the combinatorics of suffix and factor automata, Optimal bounds for computing \({\alpha}\)-gapped repeats, An extension of the Lyndon-Schützenberger result to pseudoperiodic words, Combinatorics on partial word correlations, Optimality of some algorithms to detect quasiperiodicities, A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms, Alignment-free sequence comparison using absent words, Cartesian and Lyndon trees, The extended equation of Lyndon and Schützenberger, Internal dictionary matching, Inverse Lyndon words and inverse Lyndon factorizations of words, Absent words in a sliding window with applications, Indexing weighted sequences: neat and efficient, String periods in the order-preserving model, Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis, Efficient pattern matching in elastic-degenerate strings, Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order, The exact multiple pattern matching problem solved by a reference tree approach, Universal reconstruction of a string, Constructing antidictionaries of long texts in output-sensitive space, Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence, Repetitions in strings: algorithms and combinatorics, Minimisation of automata, On overabundant words and their application to biological sequence analysis, Average-optimal string matching, Partial derivative automaton by compressing regular expressions, Global and local sequence alignment with a bounded number of gaps, Quantum algorithm for learning secret strings and its experimental demonstration, Circular Sequence Comparison with q-grams, Universal Reconstruction of a String, ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS, An aperiodicity problem for multiwords, Cross-bifix-free sets generation via Motzkin paths, String Powers in Trees, Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance, Border Correlations, Lattices, and the Subgraph Component Polynomial, Computing Primitively-Rooted Squares and Runs in Partial Words, Constructing Words with High Distinct Square Densities, Fast detection of specific fragments against a set of sequences, Absent Subsequences in Words, On-Line Pattern Matching on Uncertain Sequences and Applications, String Covering: A Survey, Quantum algorithm for lexicographically minimal string rotation, Elastic-degenerate string matching with 1 error, Unnamed Item, Subsequences in bounded ranges: matching and analysis problems, Near-optimal quantum algorithms for string problems, A Filtering Technique for All Pairs Approximate Parameterized String Matching, Representing prefix and border tables: results on enumeration, The longest common substring problem, Unnamed Item, Unnamed Item, Palindromic Decompositions with Gaps and Errors, Efficient Computation of 2-Covers of a String., Longest Common Factor After One Edit Operation, Efficient Seeds Computation Revisited, Forty Years of Text Indexing, Unnamed Item, Unnamed Item, Building Phylogeny with Minimal Absent Words, Creating improvisations on chord progressions using suffix trees, Finite Automata for Generalized Approach to Backward Pattern Matching, Repetition Detection in a Dynamic String, Circular pattern matching with \(k\) mismatches, Efficient validation and construction of border arrays and validation of string matching automata, Longest common substring made fully dynamic, An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words, Dichotomic Selection on Words: A Probabilistic Analysis, Quasi-Linear-Time Algorithm for Longest Common Circular Factor, A Linear-Time Algorithm for Seeds Computation, Optimal Computation of Overabundant Words, Efficient Identification of k-Closed Strings, Elastic-Degenerate String Matching via Fast Matrix Multiplication
