Constant-space string-matching in sublinear average time

DOI10.1016/S0304-3975(98)00259-XMaRDI QIDQ1292492zbMATH OpenOpenAlexWikidataFDO

Authors Maxime Crochemore, Leszek Gąsieniec, Wojciech Rytter

Publication date 21 June 1999

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

Full work available at URL https://doi.org/10.1016/s0304-3975(98)00259-x

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• scientific article; zbMATH DE number 4090814
• A New String Matching Algorithm
• Constant-time word-size string matching
• Average optimal string matching in packed strings
• Combinatorial Pattern Matching

Cites work

• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 826052 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• Fast Pattern Matching in Strings
• Fast algorithms for two dimensional and multiple pattern matching
• On improving the worst case running time of the Boyer-Moore string matching algorithm
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• Speeding up two string-matching algorithms
• The Complexity of Pattern Matching for a Random String
• The zooming method: A recursive approach to time-space efficient string-matching
• Time-space-optimal string matching
• Two-way string-matching

Cited in

(6)

• Complexity of substring search in a set of strings
• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• scientific article; zbMATH DE number 2086229 (Why is no real title available?)
• Algorithms – ESA 2005
• An artificial neural network based approach for online string matching/filtering of large databases
• scientific article; zbMATH DE number 4090814 (Why is no real title available?)

This page was built for publication: Constant-space string-matching in sublinear average time

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