𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Comparison Complexity of the String Prefix-Matching Problem

✍ Scribed by Dany Breslauer; Livio Colussi; Laura Toniolo

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
525 KB
Volume
29
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we study the exact comparison complexity of the string prefixmatching problem in the deterministic sequential comparison model with equality tests. We derive almost tight lower and upper bounds on the number of symbol comparisons required in the worst case by on-line prefix-matching algorithms for any fixed pattern and variable text. Unlike previous results on the comparison complexity of string-matching and prefix-matching algorithms, our bounds are almost tight for any particular pattern. We also consider the special case where the pattern and the text are the same string. This problem, which we call the string self-prefix problem, is similar to the pattern preprocessing step of the Knuth᎐Mor-ris᎐Pratt string-matching algorithm that is used in several comparison efficient

πŸ“œ SIMILAR VOLUMES

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

The complexity of the matching-cut probl
The complexity of the matching-cut problem for planar graphs and other graph classes
✍ Paul Bonsma πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg