notes the kmp algorithm is described by knuthmorrisand pratt in their journal article [ ]and boyer and moore describe their algorithm in journal article published the same year [ in their articlehoweverknuth et al [ also prove that the boyer-moore algorithm runs in linear time more recentlycole [ shows that the boyer-moore algorithm makes at most character comparisons in the worst caseand this bound is tight all of the algorithms discussed above are also discussed in the book by aho [ ]albeit in more theoretical frameworkincluding the methods for regular-expression pattern matching the reader interested in further study of string pattern-matching algorithms is referred to the book by stephen [ and the book by aho [ ]and crochemore and lecroq [ dynamic programming was developed in the operations research community and formalized by bellman [ the trie was invented by morrison [ and is discussed extensively in the classic sorting and searching book by knuth [ the name "patriciais short for "practical algorithm to retrieve information coded in alphanumeric[ mccreight [ shows how to construct suffix tries in linear time an introduction to the field of information retrievalwhich includes discussion of search engines for the webis provided in the book by baeza-yates and ribeiro-neto [