Skip to content
Exact Online String Matching

BSDM using q-grams and shift-xor

Variant of Backward SNR DAWG Matching. It computes the DAWG assuming a super alphabet on q-grams of the pattern. The q-grams are associated to a fingerprint value computed by using a shift-xor hash function.

Appeared in:

  • [42]: Faro, S.: Evaluation and improvement of fast algorithms for exact matching on genome sequences. In: 3rd Internanional Conference on Algorithms for Computational Biology. Lecture Notes in Computer Science, Springer (2016)