k-difference matching in amortized linear time for all the words in a text

Given a text x of length n, we study the problem of solving the k-difference problem for all the words, either with fixed or variable length, taken from the text itself. The result finds its application in pattern discovery in biosequences where over- or under-represented words are extracted from the input sequences. The proposed algorithm runs in amortized linear time per word. This improves the complexity obtained by applying well-known algorithms to each of the O(n) fixed length words or O(n2) variable length words in x by factor of k, , or , depending on the chosen algorithm. The space required is O(n) if we just count the occurrences, or O(n2) if we also store the positions. This second scenario can be used as the basis for other applications, such as searching gapped factors with mismatches or approximate pattern matching extended to any word.