Time-space-optimal string matching
From MaRDI portal
Publication:1838329
DOI10.1016/0022-0000(83)90001-6zbMath0509.68101OpenAlexW4210245951MaRDI QIDQ1838329
Publication date: 1983
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(83)90001-6
Related Items (49)
String-matching cannot be done by a two-head one-way deterministic finite automaton ⋮ On maximal suffixes and constant-space linear-time versions of KMP algorithm. ⋮ Efficient string matching with k mismatches ⋮ Finding the leftmost critical factorization on unordered alphabet ⋮ Permuted scaled matching ⋮ Approximating LZ77 via Small-Space Multiple-Pattern Matching ⋮ Squares, cubes, and time-space efficient string searching ⋮ String matching with simple devices ⋮ An 0(1) time algorithm for string matching ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ Multiple filtration and approximate pattern matching ⋮ Fast string matching with k differences ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ The zooming method: A recursive approach to time-space efficient string-matching ⋮ Matching patterns in strings subject to multi-linear transformations ⋮ Online Detection of Repetitions with Backtracking ⋮ Searching of gapped repeats and subrepetitions in a word ⋮ Simple real-time constant-space string matching ⋮ Confluence of one-rule Thue systems ⋮ Finding approximate repetitions under Hamming distance. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ String matching with weighted errors ⋮ On the number of gapped repeats with arbitrary gap ⋮ An algorithmic toolbox for periodic partial words ⋮ Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays ⋮ Partial words and the critical factorization theorem revisited ⋮ How the character comparison order shapes the shift function of on-line pattern matching algorithms ⋮ Streaming pattern matching with \(d\) wildcards ⋮ String-matching on ordered alphabets ⋮ Real-Time Streaming String-Matching ⋮ Simple Real-Time Constant-Space String Matching ⋮ A time-space tradeoff for language recognition ⋮ Identifying periodic occurrences of a template with applications to protein structure ⋮ Linear-time computation of local periods ⋮ Partial words and the critical factorization theorem ⋮ Space efficient search for maximal repetitions ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Periodicity in data streams with wildcards ⋮ Simple and efficient string matching with k mismatches ⋮ Fast parallel and serial multidimensional approximate array matching ⋮ Reasoning about strings in databases ⋮ Periodicity and the golden ratio ⋮ Unbordered partial words ⋮ On primary and secondary repetitions in words ⋮ Repetitions in strings: algorithms and combinatorics ⋮ Constant-space string-matching in sublinear average time ⋮ A multidimensional critical factorization theorem ⋮ Alphabet dependence in parameterized matching
Cites Work
- Unnamed Item
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Linear-time string-matching using only a fixed number of local storage locations
- On improving the worst case running time of the Boyer-Moore string matching algorithm
- A fast string searching algorithm
- Efficient randomized pattern-matching algorithms
- Saving Space in Fast String-Matching
- Real-time recognition of substring repetition and reversal
- Fast Pattern Matching in Strings
- Uniqueness Theorems for Periodic Functions
This page was built for publication: Time-space-optimal string matching
