O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

31

String Searching

Andrzej Ehrenfeucht

University of Colorado

Ross M. McConnell

Colorado State University

31.1Introduction

31.2Preliminaries

31.3The DAWG

A Simple Algorithm for Constructing the DAWGConstructing the DAWG in Linear Time

31.4The Compact DAWG

Using the Compact DAWG to Find the Locations of a String in the TextVariations and Applications

31.5The Position Heap

Building the Position HeapQuerying the Position HeapTime BoundsImprovements to the Time Bounds

References

31.1Introduction

Searching for occurrences of a substring in a text is a common operation familiar to anyone who uses a text editor, word processor, or web browser. It is also the case that algorithms for analyzing textual databases can generate a large number of searches. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required