Skip to main content
6 of 8
edited tags
ilia
  • 153
  • 4

Matching two sequences between each other

Given the sequence of symbols A (contains ~10,000 symbols) and sequence of blocks B (contains ~3,000 blocks, ~30 symbols inside each block) I need to exclude some blocks from sequence B so that symbols inside sum of blocks from B will be equal to A. Blocks cannot be modified or replaced, they have fixed position in sequence.

Sequences example

I'm looking for some computation efficient method to solve this problem as Levenshtein distance looks too expensive for this task. Besides, Levenshtein distance works with individual symbols, it is not entirely clear how to move from block to symbols in this case.

ilia
  • 153
  • 4