Pattern Distance, Normalized Hamming Distance under Shifts

Given a text TT of length nn and a pattern PP of length mm, both consisting of numbers, output the normalised Hamming distance under shifts (dH+(i)=min⁡α∣{j∣α+P[j]≠T[i+j]}∣d_H^+(i) = \min_{\alpha} \left| \{ j \mid \alpha+P[j] \neq T[i+j] \} \right|) at every position i∈{0,…,n−m}i\in \{0, \dots, n-m\} of the text.

Parameters

  • mm: pattern length
  • nn: length of searchable text

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table