Lecture Notes Series on Computing

                          STRING SEARCHING ALGORITHMS

                       by Graham A Stephen (Univ Wales)

  String searching is a subject of both theoretical and practical interest in
computer science.  This book presents a bibliographic overview of the field and
an anthology of detailed descriptions of the principal algorithms available.
The aim is twofold: on the one hand, to provide an easy-to-read comparison of
the available techniques in each area, and on the other, to furnish the reader
with a reference to in-depth descriptions of the major algorithms.
  Topics covered include methods for finding exact and approximate string
matches, calculating `edit' distances between strings, finding common sequences
and finding the longest repetitions within strings.  For clarity, all the
algorithms are presented in a uniform format and notation.

Contents: Introduction; String Matching; String Distance and Common Sequences;
          Suffix Trees; Approximate String Matching; Repeated Substrings.

Readership: Computer scientists, software developers, computational biologists.

250pp (approx), Pub date: October 1994, ISBN 981-02-1829-X, US$ 34/UK pounds 25

  For further information, please contact
    Marketing Department, World Scientific Publishing Co Pte Ltd
at fax no: (65) 382 5919 or e-mail address: worldscp@singnet.com.sg

-------------------------------------------------------------------------------

                               DETAILED CONTENTS

1  Introduction

2  String Matching
   2.1  Overview
        2.1.1  Brute Force
        2.1.2  Knuth-Morris-Pratt and Boyer-Moore Approaches
        2.1.3  Hashing Functions
        2.1.4  Comparative Performance
        2.1.5  Popularity
        2.1.6  Multiple-String Searches
   2.2  Algorithms in Detail
        2.2.1  Brute Force
        2.2.2  Knuth-Morris-Pratt
        2.2.3  Boyer-Moore
        2.2.4  Boyer-Moore-Horspool
        2.2.5  Sunday --- Quick Search, Maximal Shift, and Optimal Mismatch
        2.2.6  Hume and Sunday --- Tuned Boyer-Moore and Least Cost
        2.2.7  Harrison
        2.2.8  Karp-Rabin
   2.3  Further Reading

3  String Distance and Common Sequences
   3.1  Overview
        3.1.1  String Distance Measures
        3.1.2  String Distance and Longest Common Subsequence
        3.1.3  Comparative Performance
        3.1.4  Related Problems
   3.2  Algorithms in Detail
        3.2.1  Wagner-Fischer
        3.2.2  Hirschberg
        3.2.3  Hunt-Szymanski
        3.2.4  Masek-Paterson
        3.2.5  Ukkonen
        3.2.6  Heaviest Common Subsequence
   3.3  Further Reading

4  Suffix Trees
   4.1  Overview
        4.1.1  Suffix Tries
        4.1.2  From Suffix Trie to Suffix Tree
   4.2  Algorithms in Detail
        4.2.1  Brute Force
        4.2.2  McCreight
        4.2.3  Ukkonen
   4.3  Further Reading

5  Approximate String Matching
   5.1  Overview
        5.1.1  String Matching with k Mismatches
        5.1.2  String Matching with k Differences
        5.1.3  String Matching with Don't-Cares
        5.1.4  Application Areas
        5.1.5  Dedicated Hardware and Parallel Algorithms
   5.2  Algorithms in Detail
        5.2.1  Landau-Vishkin k-mismatches
        5.2.2  Shift-Add
        5.2.3  Tarhio-Ukkonen k-mismatches
        5.2.4  Baeza-Yates--Perleberg k-mismatches
        5.2.5  Dynamic Programming k-differences
        5.2.6  Landau-Vishkin k-differences
        5.2.7  Chang-Lawler k-differences
        5.2.8  Chang-Lampe k-differences
        5.2.9  Wu-Manber k-differences
   5.3  Further Reading

6  Repeated Substrings
   6.1  Overview
        6.1.1  Repetitions
        6.1.2  Longest Repeated Substrings
   6.2  Algorithms in Detail
        6.2.1  Brute Force
        6.2.2  Suffix Trees

A  Asymptotic Notation

B  String Symbology

C  Glossary

D  Bibliography

Index