Return to Question

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.

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.

Some obvious ideas:

• If sequence $A$ does not contain block $b_i$, then $b_i$ can be excluded from $B$
• If (a) block $b_i$ is not subsequence of any other block in $B$; (b) there are no blocks inside $B$, that can be subsequence of $b_i$; (c) $b_i$ is the only match to $a_j$; the whole task can be split into two separate pieces

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.

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.

Some obvious ideas:

• If sequence $A$ does not contain block $b_i$, then $b_i$ can be excluded from $B$
• If there are no blocks inside $B$, that are subsequences of $b_i$ and $b_i$ is the only match to subsequence $a_j$, the whole task can be split into two separate pieces

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.

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.

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.

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.

Some obvious ideas:

• If sequence $A$ does not contain block $b_i$, then $b_i$ can be excluded from $B$
• If (a) block $b_i$ is not subsequence of any other block in $B$; (b) there are no blocks inside $B$, that can be subsequence of $b_i$; (c) $b_i$ is the only match to $a_j$; the whole task can be split into two separate pieces