On the Comparison Complexity of the String Prefix-Matching Problem

DOI10.1006/JAGM.1998.0948MaRDI QIDQ4217300zbMATH OpenOpenAlexFDO

Authors Dany Breslauer, Livio Colussi, Laura Toniolo

Publication date 18 May 1999

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/3b60002e9dfaa8a3cad73d1dcf27820c46e47201

zbMATH Keywords

on-line prefix-matching algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Recommendations

• Tight comparison bounds for the string prefix-matching problem
• Tighter Lower Bounds on the Exact Complexity of String Matching
• Efficient comparison based string matching

Cited in

(6)

• Validating the Knuth-Morris-Pratt failure function, fast and online
• On the weak prefix-search problem
• Tighter Lower Bounds on the Exact Complexity of String Matching
• Linear-time computation of prefix table for weighted strings {\&} applications
• Fast prefix matching of bounded strings
• Tight comparison bounds for the string prefix-matching problem

This page was built for publication: On the Comparison Complexity of the String Prefix-Matching Problem

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