🚀 go-pugleaf

Archive-name: auto/bionet.info-theory/String-Matching-Report

| Further to a string matching query posed some months ago,
| I can make available a report containing a review of various
| string matching algorithms. The opening and closing sections
| of the report may not be of general interest, but it does
| include descriptions of the following:
| 
| 
|      String Matching
|
|           Knuth-Morris-Pratt (1977)
|           Boyer-Moore (1977)
|           Boyer-Moore-Horspool (1980)
|           Sunday --- Quick Search, Maximal Shift, and Optimal Mismatch (1990)
|           Hume and Sunday --- Tuned Boyer-Moore and Least Cost (1991)
|           Harrison (1971)
|           Karp-Rabin (1987)
|  
|      String Distance and Longest Common Subsequence
|      
|           Wagner-Fischer (1974)
|           Hirschberg (1975)
|           Hunt-Szymanski (1977)
|           Masek-Paterson (1980)
|           Ukkonen (1983)
|           Heaviest Common Subsequence (Jacobson & Vo, 1992)
| 
|      Approximate String Matching
|     
|           Landau-Vishkin k-mismatch (1985)
|           Landau-Vishkin k-difference (1986)
| 
|      Longest Repeated Substring
| 
|           McCreight (1976)
|           Baker (1992)     
| 
| 
| Send requests, if any, via email, specifying whether A4 or the
| default latex paper size and margins are required for the
| uuencoded compressed postscript file.

Due to the overwhelming volume of requests for this report, 
it is now available via anonymous ftp from venus.sees.bangor.ac.uk
(147.143.7.12) in directory pub/graham.  The following files
are available:

     TR92gas01.tex.Z      113999  |
     TR92gas01.dvi.Z      194375  |    A4 paper with narrow margins
     TR92gas01.ps.Z       339475  |

     TR92gas01.us.dvi.Z   199867  |
     TR92gas01.us.ps.Z    345361  |    default paper and margins


To clear up some confusion, A4 is (allegedly) an international
standard paper size (210x297 mm).  The latex defaults (presumably) are
for `letter' size paper (8.5x11 inch) and use rather excessive margins.
Note that the page counts are as follows:

     A4 version :  iv + 103
     default    :   v + 138

Feel free to customise the latex source to your own requirements (this
may involve a certain amount of fiddling around to avoid too many
`overfull hboxes', but there you go!)

Anyone without access to ftp wishing a copy of the report may still
request it via email, and I'll try to post it out (as time and mailer
spool area permit!)

--
graham a stephen                    
(e-mail: graham@sees.bangor.ac.uk)        

``One measures a circle beginning anywhere'' -- Charles Hoy Fort (1874-1932)