Tight comparison bounds for the string prefix-matching problem
From MaRDI portal
Publication:685487
DOI10.1016/0020-0190(93)90156-4zbMATH Open0802.68066OpenAlexW2048532915MaRDI QIDQ685487FDOQ685487
Livio Colussi, Laura Toniolo, Dany Breslauer
Publication date: 11 December 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/1524
Recommendations
- On the Comparison Complexity of the String Prefix-Matching Problem
- Fast prefix matching of bounded strings
- Tighter Upper Bounds on the Exact Complexity of String Matching
- Tighter Lower Bounds on the Exact Complexity of String Matching
- scientific article; zbMATH DE number 1256698
- On the Exact Complexity of String Matching: Upper Bounds
- On the Exact Complexity of String Matching: Lower Bounds
- Exact bounds on the complexity of sequential string matching algorithms
- Tight chip area lower bounds for string matching
- On the lower bound for parallel string matching
Cites Work
- A fast string searching algorithm
- Fast Pattern Matching in Strings
- Title not available (Why is that?)
- Efficient comparison based string matching
- On the Exact Complexity of String Matching: Lower Bounds
- On the Exact Complexity of String Matching: Upper Bounds
- Correctness and efficiency of pattern matching algorithms
- Title not available (Why is that?)
- On the Worst-Case Behavior of String-Searching Algorithms
Cited In (6)
- On the weak prefix-search problem
- Exact bounds on the complexity of sequential string matching algorithms
- Optimal parallel algorithms for Prefix Matching
- Title not available (Why is that?)
- Linear-time computation of prefix table for weighted strings {\&} applications
- How the character comparison order shapes the shift function of on-line pattern matching algorithms
This page was built for publication: Tight comparison bounds for the string prefix-matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685487)
