From: graham@sees.bangor.ac.uk (Graham A Stephen)
Newsgroups: alt.books.technical
Subject: Book Announcement
Date: 22 Sep 1994 07:57:57 -0500

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 and
computational biologists.

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


For further information, please contact the 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