One common technique is to only look at all $k$-mers of a sequence: For each input sequence we can store all the consecutive subsequences of length \(k\) occuring in the sequence, and when such a $k$-mer occurs in two sequences, we can then check the corresponding positions in these sequences to see whether they are indeed related. Matching positions We say that two positions match (assuming a spaced seed) if the spaced k-mers induced by the spaced seed starting at these positions are the same. Find a subset of positions \(S\subseteq \N\), such that taking all windows starting at positions in \(S\) in both sequence \(A\) and \(B\) guarantees a matching starting position once every \(d\) positions.