𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm

✍ Scribed by Maxime Crochemore; Thierry Lecroq

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
678 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of $n text character comparisons when searching for a pattern in a text of length n. We exhibit a family of patterns and texts reaching this bound. We also provide a slightly improved version of the algorithm. @ 1997 Elsevier Science B.V.

πŸ“œ SIMILAR VOLUMES

Improved Bounds on the Sample Complexity
Improved Bounds on the Sample Complexity of Learning
✍ Yi Li; Philip M. Long; Aravind Srinivasan πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 137 KB

We present a new general upper bound on the number of examples required to estimate all of the expectations of a set of random variables uniformly well. The quality of the estimates is measured using a variant of the relative error proposed by Haussler and Pollard. We also show that our bound is wit

On the cost of recomputing: Tight bounds
On the cost of recomputing: Tight bounds on pebbling with faults
✍ Yonatan Aumann; Judit Bar-Ilan; Uriel Feige πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 184 KB

We introduce a formal framework to study the time and space complexity of computing with faulty memory. For the fault-free case, time and space complexities were studied using the "pebbling game" model. We extend this model to the faulty case, where the content of memory cells may be erased. The mod