Tight comparison bounds for the string prefix-matching problem
The authors study the following generalization of the standard string matching problem, called string prefix-matching problem. Given a text string T\([1\dots n]\) and a pattern string P\([1\dots n]\), compute an integer array \(\pi [1\dots n]\) such that for each \(i\) \((1 \leq i \leq n)\), \(\pi [i] \leq m\) and \(\pi [i]\) is the largest integer satisfying T\([i..i + \pi [i] - 1]=\text{P}[1..\pi [i]]\). I. e., \(\pi[i]\) gives the longest prefix of the pattern P that coincides with a substring of the text T starting in position \(i\). In this paper the authors give upper and lower bounds for the exact complexity of the string prefix-matching in the deterministic sequential comparison model.
- 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
- 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
- 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)
