Pattern Distance, Normalized Hamming Distance under Shifts and Scaling

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 and scaling (dH+(i)=min⁡α,β∣{j∣α+βP[j]≠T[i+j]}∣d_H^+(i) = \min_{\alpha, \beta} \left| \{ j \mid \alpha+\beta 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