Saving comparisons in the Crochemore-Perrin string-matching algorithm

DOI10.1016/0304-3975(95)00068-2MaRDI QIDQ1365685zbMATH OpenOpenAlexFDO

Authors Dany Breslauer

Publication date 7 September 1997

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

Full work available at URL https://hal.inria.fr/inria-00074535/file/RR-2137.pdf

zbMATH Keywords

constant-space string-matching algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Efficient comparison based string matching
• On the Exact Complexity of String Matching: Upper Bounds
• Publication:3468609

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3608306 (Why is no real title available?)
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 826052 (Why is no real title available?)
• k one-way heads cannot do string-matching
• A fast string searching algorithm
• Correctness and efficiency of pattern matching algorithms
• Efficient comparison based string matching
• Fast Pattern Matching in Strings
• Fastest Pattern Matching in Strings
• Linear-time string-matching using only a fixed number of local storage locations
• On the Exact Complexity of String Matching: Lower Bounds
• On the Exact Complexity of String Matching: Upper Bounds
• Periods in strings
• Saving Space in Fast String-Matching
• Speeding up two string-matching algorithms
• String-matching cannot be done by a two-head one-way deterministic finite automaton
• String-matching on ordered alphabets
• The Boyer–Moore–Galil String Searching Strategies Revisited
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Three one-way heads cannot do string matching
• Time-space-optimal string matching
• Two-way string-matching
• Uniqueness Theorems for Periodic Functions

Cited in

(10)

• scientific article; zbMATH DE number 2052916 (Why is no real title available?)
• Efficient comparison based string matching
• The zooming method: A recursive approach to time-space efficient string-matching
• On maximal suffixes and constant-space linear-time versions of KMP algorithm.
• Simple real-time constant-space string matching
• Simple real-time constant-space string matching
• Constant-space string-matching in sublinear average time
• Characteristic Sturmian words are extremal for the critical factorization theorem
• scientific article; zbMATH DE number 2086229 (Why is no real title available?)
• The Ehrenfeucht-Silberger problem

This page was built for publication: Saving comparisons in the Crochemore-Perrin string-matching algorithm

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