Fast string matching algorithms

String matching algorithms constitute a major chunk of computation time in general. Amir et al have devised a new algorithm which finds all locations where the target string differs from the source string by at most k mismatches in O(n sqrt(k log(k))).