Two-way string-matching
From MaRDI portal
Publication:4302850
DOI10.1145/116825.116845zbMath0808.68063OpenAlexW2017497752MaRDI QIDQ4302850
Maxime Crochemore, Dominique Perrin
Publication date: 29 September 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/116825.116845
Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10) Parallel algorithms in computer science (68W10) Computing methodologies for text processing; mathematical typography (68U15)
Related Items (47)
On maximal suffixes and constant-space linear-time versions of KMP algorithm. ⋮ Indeterminate string factorizations and degenerate text transformations ⋮ Density of Critical Factorizations ⋮ Dictionary Matching in a Stream ⋮ Approximating LZ77 via Small-Space Multiple-Pattern Matching ⋮ Squares, cubes, and time-space efficient string searching ⋮ String matching with simple devices ⋮ Critical factorisation in square-free words ⋮ The structure of subword graphs and suffix trees of Fibonacci words ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ The zooming method: A recursive approach to time-space efficient string-matching ⋮ Inferring strings from Lyndon factorization ⋮ Words with unbounded periodicity complexity ⋮ Simple real-time constant-space string matching ⋮ A note on a simple computation of the maximal suffix of a string ⋮ Constructing Words with High Distinct Square Densities ⋮ Fast parallel Lyndon factorization with applications ⋮ Bifix codes and Sturmian words ⋮ Towards optimal packed string matching ⋮ On the Relation between Periodicity and Unbordered Factors of Finite Words ⋮ An algorithmic toolbox for periodic partial words ⋮ Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays ⋮ The Ehrenfeucht-Silberger problem ⋮ Partial words and the critical factorization theorem revisited ⋮ How the character comparison order shapes the shift function of on-line pattern matching algorithms ⋮ String-matching on ordered alphabets ⋮ On the density of Lyndon roots in factors ⋮ Simple Real-Time Constant-Space String Matching ⋮ Generic Algorithms for Factoring Strings ⋮ Efficient CRCW-PRAM algorithms for universal substring searching ⋮ Linear-time computation of local periods ⋮ On unique factorizations of primitive words. ⋮ Partial words and the critical factorization theorem ⋮ A proof of the extended Duval's conjecture ⋮ Necklaces and bracelets in R ⋮ Characteristic Sturmian words are extremal for the critical factorization theorem ⋮ Unnamed Item ⋮ Recurrence and periodicity in infinite words from local periods ⋮ Periods in extensions of words ⋮ Watson-Crick Conjugate and Commutative Words ⋮ The factors analysis and algorithm implementation of single-pattern matching ⋮ Unbordered partial words ⋮ Repetitions in strings: algorithms and combinatorics ⋮ Constant-space string-matching in sublinear average time ⋮ A multidimensional critical factorization theorem ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Longest Lyndon Substring After Edit
This page was built for publication: Two-way string-matching
