Tight comparison bounds for the string prefix-matching problem
From MaRDI portal
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
- Correctness and efficiency of pattern matching algorithms
- Efficient comparison based string matching
- Fast Pattern Matching in Strings
- scientific article; zbMATH DE number 1256698 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- On the Exact Complexity of String Matching: Lower Bounds
- On the Exact Complexity of String Matching: Upper Bounds
- On the Worst-Case Behavior of String-Searching Algorithms
Cited in
(8)- Exact bounds on the complexity of sequential string matching algorithms
- On the weak prefix-search problem
- On the Comparison Complexity of the String Prefix-Matching Problem
- scientific article; zbMATH DE number 1256698 (Why is no real title available?)
- Optimal parallel algorithms for Prefix Matching
- Linear-time computation of prefix table for weighted strings {\&} applications
- String range matching
- 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)
