partial numerical array - pattern matching

Question

I have a linear numerical array source and I want to find/match test array as pattern :

source = [39,36,23,21,28,36,30,22,34,37]
test = [36,23,21,28]

we can use brute force or similar method for finding the exact match, by checking test array from index 0 to len(source)-len(test)

but in our problem, we can accept this pattern too ( order is important )

test = [36,24,21,28] // changed 23 to 24

since we have many different ways of solving this problem ( maybe fuzzy!), I want to know the title of some solutions.

It's not clear from your question what a correct match should be? Does the test have to be a consecutive subsequence with minor modification? Does order matter or a sequence with the same numbers in a different order can also be a match? Are you interested in a similarity score? — Erwan, Jan 27 '20 at 21:00
the big problem is I am in the middle of a problem without any background knowledge.The answer for your first and second questions are . the order is important too. lets put it in this way , I can accept the array as matched with ±2 units change for each element. — Mironline, Jan 27 '20 at 21:24

score 1 · Answer 1 · answered Jan 27 '20 at 22:25

According to your definition (consecutive, order matters, max +/-2 difference), it's not a fuzzy matching case. It's just a minor variant of searching a subsequence:

for i=0 to len(source)-len(test) {
  j=0
  while (j<len(test)) && (abs(source[i+j]-test[j]) <= 2) {
    j++
  if (j == len(test)) { 
     // match found
  }
}

This is the simple version, in case efficiency is an issue there is a more efficient version using dynamic programming.

partial numerical array - pattern matching

1 Answers1