How to find longest possible identical sequence in Array A and B?

Question

You have to arrays of single digit numbers. (0 - 9).

A = [....1 billion elements....];
B = [3,5,8,1,2,5,8,3,4,9,1,0,2];

I want to find combo of as few as possible subsets that of array B in A.

So whole Array B could be in Array A by coincidence since it's very large and that would be the largest match as whole sequence is there. Or you could have subset of array B, [8,3,4,9], at index ex: i = 3800443...

Now my goal is to convert Array B to references based on Array A.

So If I give you object like this:

{
  block1: {i: 48938, len: 388},
  block2: {i: 2828, len: 3},
  ...
}

you'd be able to reconstruct array B if you had array A.

One mistake would be to go and find biggest subset only. Then the solution would have biggest subset, but not minimum amount of subsets possible.

Example:

a = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |^||^||^||^||^||      ^     ||^|

Although this has longest subset, but It ended up with 6 blocks. Whereas,

b = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |    ^    ||     ^    ||    ^   |

here each subset might not be the longest but there are fewer subsets to cover whole array.

Answer 1

Assuming all characters of $B$ are wholly contained in $A$, then this method should give you an optimal results.

Algorithm

1. Compute the longest substring $P_i$ in $A$ that is a prefix of the suffix of $B$ from $B_{i \ldots n}$. This is essentially equivalent to finding the longest common substrings between $A$ and $B$ starting at index $i$ of $B$. There are many methods of doing this, some listed below:
   1. Compute a suffix tree $T$ for the array $B$. Making sure to leave in the suffix links (these are important for back tracking and essentially make the tree like an Aho-Corasick state machine). Traverse $A$ using $T$ as a state machine. Keep track of deepest non-root node reached in $T$ for each path from root to leaf. This will take $\Theta(|B|) + \Theta(|B| + |A|) = \Theta(|B| + |A|)$.
   2. Solve this by inserting both strings $A$ and $B$ into a generalized suffix tree. Keep track of deepest common ancestor between a suffix leaf of $B$ with any other suffix leaf in $A$. This will take $\Theta(|B| + |A|)$.
   3. Least optimal, use dynamic programming, but reverse the formula so you compute longest prefix for a suffix, rather than longest suffix for a given prefix. This will take $\Theta(|B|\cdot |A|)$. (Would not recommend)
2. Sort $P$ by the index of the starting character of the prefix (i.e. in the original suffix order).
3. Let $i = 0$
4. While $i < |B|$:
   1. Let $j$ be the last index of substring $P_i$.
   2. Add substring $P_i$ to a set $S$.
   3. Let $i = j+1$
5. Return $S$ as it is the set of sequences in $A$ that minimally but completely cover $B$.

Running Time

Let $n = |B|$ and $m = |A|$:

1. Will take $O(n + m)$ because branching factor is constant (only 10 values) and if you keep it compressed and refer to indices instead of values.
2. Will take $O(n \log n)$ or $O(1)$ depending on how you structure $T$.
3. Will take $O(n)$.

Total time will be $O(m + n)$ which will be $O(m)$ for $m \gg n$.

Example

Let $$B = [0, 1, 3, 1, 2, 0]$$ $$A = [2, 1, 3, 0, 5, 1, 2, 4, 0, 1, 3, 0, 3, 1]$$

Step 1 would compute the following tree:

Step 2 should generate the following longest prefixes $P$ for suffix $S$:

$$\begin{array}{|c||r|r|} \hline B \text{ indices} & S & P \\ \hline [0\ldots 5] & 0,1,3,1,2,0 & 0,1,3 \\ \hline [1\ldots 5] & 1,3,1,2,0 & 1,3 \\ \hline [2\ldots 5] & 3,1,2,0 & 3,1 \\ \hline [3\ldots 5] & 1,2,0 & 1,2 \\ \hline [4\ldots 5] & 2,0 & 2 \\ \hline [5\ldots 5] & 0 & 0 \\ \hline \end{array}$$

We then follow steps 5, 6, and 7 to get that our set to be returned is contained of: $$P_0 = [0, 1, 3], P_3 = [1, 2], \text{ and } P_5 = [0]$$

It's also easy to think of this as the maximum number of disjoint subsequences of $B$ contained in $A$. The maximum here is 3 because there are at most 3 subsequences that have no overlapping pieces:

Maybe this visualization will help. Then we should keep track of indices along the way in $A$ (this is relatively trivial with proper manipulation), but we see $B$ can be represented by:

$$A[6 \ldots 8] \; A[4 \ldots 5] \; A[3 \ldots 3]$$ $$0,1,3 : 1,2 : 0$$