I ave a a collection of lists of objects:
$a_1$ $a_2$ $a_3$...
$b_1$ $b_2$ $b_3$...
$c_1$ $c_2$ $c_3$..
I need to merge them into a minimal possible number of lists, each list must be as long as possible. The merge does as follows:
For every consequitve pair ($x_i$, $x_{i + 1}$) within the collection, if one or more subsequences ($x_i$, $y_j$, $y_{j + 1}$, ... $y_k$, $x_{i + 1}$) exists, substitute the pair with the longest said subsequence.
After all such substitutions are made, eliminate redundant lists as follows:
for every list $x_1$, $x_2$, ... $x_m$, if for each $j$ the subsequence ($x_j$, ... $x_{j + 1}$ exists in any other list, remove the whole list.
For example, this collection of two list of strings:
"a", "sheep", "grazing"
"a", "young", "white", "sheep"
Is to be merged into
"a", "young", "white", "sheep", grazing"
This is because the subsequence in the second line
"a", "young", "white", "sheep"
can be squeezed between "a" and "sheep" of the first line, while
"sheep", "grazing", end-of-line of the first line can be squeezed between "sheep", end-of-line of the second line.
Likewise, if there is a list A1, ... AN in one of the lines, and another line starts with AN or ends with A1, the substitution is to occur.
However,
"a", "lonely", "sheep", "grazing"
"a", "young", "white", "sheep"
can't be merged into one list, because we don't know whether "lonely" should go before or after "young", before or after "white", etc.
So this case is to be partially merged into
"a", "lonely", "sheep", "grazing"
"a", "young", "white", "sheep", "grazing"
Pseudocode welcome.
