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,,nm}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