String-matching on ordered alphabets

DOI10.1016/0304-3975(92)90134-2zbMath0747.68021OpenAlexW2076967798MaRDI QIDQ1190451

Maxime Crochemore

Publication date: 26 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90134-2

zbMATH Keywords

linear time algorithmstring-matching algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items (12)

On maximal suffixes and constant-space linear-time versions of KMP algorithm. ⋮ Engineering a lightweight external memory suffix array construction algorithm ⋮ Squares, cubes, and time-space efficient string searching ⋮ String matching with simple devices ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ Simple real-time constant-space string matching ⋮ A note on a simple computation of the maximal suffix of a string ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ An algorithmic toolbox for periodic partial words ⋮ How the character comparison order shapes the shift function of on-line pattern matching algorithms ⋮ Simple Real-Time Constant-Space String Matching ⋮ Non-Overlapping Indexing - Cache Obliviously

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal parallel detection of squares in strings
• Time-space-optimal string matching
• A fast string searching algorithm
• Factorizing words over an ordered alphabet
• String Matching in Real Time
• Fast Pattern Matching in Strings
• Two-way string-matching

This page was built for publication: String-matching on ordered alphabets