Send email to dave
davidhbrown.usTables constructed for Knuth-Morris-Pratt algorithm and Boyer-Moore algorithm after Sara Baase,Computer Algorithms: Introduction to Design and Analysis (Addison-Wesley Series in Computer Science), 1988 (2nd Ed). ISBN 0201060353.
JavaScript to calculate the tables is in spat.js; just click on over to see what mistakes I might have made... watch, this won't even show up on the final! (URI CSC440, Fall 2009) Results have been checked against our homework #3 ("abracadabra" and "astracastra" -- which I totally messed up; should have written this sooner!), exam #2 ("aaaa"), and the examples in the above reading (KMP: "abababcb"; BM: "wowwow").
| Knuth-Morris-Pratt: fail | Boyer-Moore charJump | Boyer-Moore matchJump |
|---|---|---|
display triggered by typing a pattern |
|
Note that this page seems to be perfectly happy with Unicode values. If (like me) you don't know how to enter multibyte characters head over here (new window) to find some to copy/paste.The algorithms don't switch reading direction or anything like that, though!
Copyright (C) 2009,
David H. Brown. Don't steal my stuff; I won't steal yours. But I'd probably
be really happy to share.
Send email to davedavidhbrown.us