Skip to main content

Blog Archive for potty during May 2012

Boyer-Moore (BM) Overview According to Wikipedia, the Boyer-Moore algorithm "is an efficient string searching algorithm that is the standard benchmark for practical string search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-...
Knuth-Morris-Pratt (KMP) Overview According to Wikipedia, the Knuth-Morris-Pratt algorithm "searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters". Being 'A' the...