String-matching on ordered alphabets

DOI10.1016/0304-3975(92)90134-2MaRDI QIDQ1190451zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Publication:3468609
• scientific article; zbMATH DE number 1615293
• The zooming method: A recursive approach to time-space efficient string-matching
• A New String Matching Algorithm
• Simple Optimal String Matching Algorithm

Cites work

• scientific article; zbMATH DE number 4007744 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• A fast string searching algorithm
• Factorizing words over an ordered alphabet
• Fast Pattern Matching in Strings
• Optimal parallel detection of squares in strings
• String Matching in Real Time
• Time-space-optimal string matching
• Two-way string-matching

Cited in

(22)

• Center and distinguisher for strings with unbounded alphabet
• Quantum algorithm for lexicographically minimal string rotation
• String matching with simple devices
• Efficient parameterized pattern matching in sublinear space
• Non-overlapping indexing in BWT-runs bounded space
• scientific article; zbMATH DE number 1615293 (Why is no real title available?)
• A note on a simple computation of the maximal suffix of a string
• Engineering a lightweight external memory suffix array construction algorithm
• Non-overlapping indexing -- cache obliviously
• Squares, cubes, and time-space efficient string searching
• How the character comparison order shapes the shift function of on-line pattern matching algorithms
• Simple real-time constant-space string matching
• Enhanced string factoring from alphabet orderings
• scientific article; zbMATH DE number 1751384 (Why is no real title available?)
• An algorithmic toolbox for periodic partial words
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• scientific article; zbMATH DE number 4135398 (Why is no real title available?)
• scientific article; zbMATH DE number 4078846 (Why is no real title available?)
• Improved pattern-scan-order algorithms for string matching
• Simple real-time constant-space string matching
• On maximal suffixes and constant-space linear-time versions of KMP algorithm.
• A New String Matching Algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190451)