Constant-space string-matching in sublinear average time

DOI10.1016/S0304-3975(98)00259-XzbMATH Open0916.68113OpenAlexW3035186240WikidataQ61677968 ScholiaQ61677968MaRDI QIDQ1292492FDOQ1292492

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

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Two-way string-matching
• Title not available (Why is that?)
• Speeding up two string-matching algorithms
• On improving the worst case running time of the Boyer-Moore string matching algorithm
• Fast Pattern Matching in Strings
• Title not available (Why is that?)
• Time-space-optimal string matching
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• The zooming method: A recursive approach to time-space efficient string-matching
• Title not available (Why is that?)
• The Complexity of Pattern Matching for a Random String
• Fast algorithms for two dimensional and multiple pattern matching

Cited In (6)

• Complexity of substring search in a set of strings
• Title not available (Why is that?)
• Algorithms – ESA 2005
• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• An artificial neural network based approach for online string matching/filtering of large databases
• Title not available (Why is that?)

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)