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