The streaming k-mismatch problem

The central problem of text processing is pattern matching: given two strings (a pattern and a text), find all fragments of the text matching the pattern. In exact matching, solely equal strings match; however, this condition is relaxed in many variants of approximate pattern matching. In the k-mismatch problem, we allow for up to k substitutions, that is, strings of the same length are assumed to match even if there are at most k mismatching characters between them.

Read more