Theorem 8.3 is from Fischer and Paterson [138]. The result used in the proof of the theorem stating that it is possible to multiply a number with M digits by a number with N digits in time O( N log M log log M) for N ? M is from Sch nhage and Strassen [206].

The algorithm K-DIFF-CUT-OFF is from Ukkonen [212]. The algorithm K-DIFF-DIAG together with its implementation with the help of the computation of common ancestors was described by Landau and Vishkin [175]. Harel and Tarjan [150] presented the first algorithm running in constant time that solves the problem of the lowest ancestor common to two nodes of a tree. An improved solution is from Schieber and Vishkin [205].

Landau and Vishkin [174] conceived the algorithm k-MISMATCHES. The size of the automaton of Section 8.3 was established by Melichar [185]. Extension and improvement on the string matching algorithm for k mismatches are by Abrahamson [85] and by Amir, Lewenstein, and Porat [91].

The approximate pattern matching for short strings as reported by the algorithm K-DIFF-SHORT-PATTERN is from Wu and Manber [218] and also from Baeza-Yates and Gonnet [99].

Another method that uses the bit-parallelism technique and is optimal consists actually of a filtration method. It considers sparse q -grams and thus avoids scanning many text positions. It is due to Fredriksson and Grabowski [141]. A notion of seeds for searching genomic sequences speed-up dramatically approximate matching algorithms.