7
$\begingroup$

Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet. Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of any of $x^-_1,\dots,x^-_n$.

Given $x^+,x^-_1,\dots,x^-_n$, I am looking to find the shortest good string $s$. Is there a reasonable algorithm for this? I am interested in a practical algorithm, even if its worst-case running time is not great. In my domain, the strings $x^+,x^-_1,\dots,x^-_n$ might be fairly long but I expect there will exist a good string $s$ that is fairly short, in case that helps.

The case $n=1$ is handled by Shortest sub-sequence of one string, that's not a sub-sequence of another string, but I need to deal with the case $n>1$.

$\endgroup$
  • 1
    $\begingroup$ My standard proposal: suffix tree? The string you're looking for is the node with smallest level among all that have only $(x^+, \_)$ as leaf. Oh, wait... subsequence? Damn. Hm. $\endgroup$ – Raphael Aug 31 '17 at 18:11
  • $\begingroup$ Is this problem without $x^+$ the dual to longest common subsequence? If so, maybe something can be done along those lines. (Enumerating common non-subsequences by increasing length would solve your problem.) $\endgroup$ – Raphael Aug 31 '17 at 18:15
  • $\begingroup$ I believe that Aryabhata's DP can be extended fairly easily to the $n > 1$ case: just use $n$ tables, one for each $x_i^-$, and then hunt for the smallest $L$ such that for each table $i$, and for some $k$, $is\_there[i, k, t, L] = false$. That will tell you the length ($L$) and the final character ($x^+[k]$), but I'm not yet sure how to extract the earlier characters... $\endgroup$ – j_random_hacker Aug 31 '17 at 19:26
  • 2
    $\begingroup$ @j_random_hacker, I don't think that works. That might pick one subsequence of $x^+$ of length $L$ that isn't a subsequence of $x^-_1$, and a different subsequence of $x^+$ of length $L$ that isn't a subsequence of $x^-_2$. (The first one might be a subsequence of $x^-_2$, and the second one a subsequence of $x^-_1$, which would be bad.) We need a single subsequence of $x^+$, not a separate one for each $x^-_i$. Or did I miss something clever about your idea? $\endgroup$ – D.W. Aug 31 '17 at 21:32
  • 3
    $\begingroup$ If you don't need absolutely the shortest subsequence, you could use the fact that, if a string $s$ is not a subsequence of any $x_i^-$, then it is also not a subsequence of any interleaving of the strings $x_i^-$. So you could try many different ways of randomly interleaving the $n$ strings $x_i^-$ into a single string, and for each such interleaving $y_j$, look for a subsequence $z_j$ of $x^+$ that avoids being a subsequence of $y_j$ using Aryabhata's DP, and pick whichever $z_j$ is shortest. $\endgroup$ – j_random_hacker Aug 31 '17 at 22:33
1
$\begingroup$

Mistakes

First of all, in the comments I made a few mistakes: Both the original claim I made about interleaving, and the comment "correcting" it (now deleted) were wrong, and separately my claim that trying all possible interleavings must yield an optimal solution was also wrong (I give a simple counterexample below). Finally, my suggestion to set $x^+ = z_j$ and iterate, or use beam search, is actually also not helpful: Whatever answer could be produced by doing this and applying Aryabhata's DP can never be better than using the original $x^+$, since all it does is reduce the size of the solution set from which the DP can pick. Sorry! Hopefully the improved version below contains no further problems...

I also noticed two mistakes in Aryabhata's DP as well. Fortunately they can both be easily repaired (see my comments on that post).

A heuristic solution using random interleavings

If you don't need absolutely the shortest subsequence, you could use the fact that, if a string $s$ is a subsequence of some $x^-_i$, then it is also a subsequence of every possible interleaving of all the strings $x^-_i$. Turning this around, if $s$ is not a subsequence of some particular interleaving of all the strings $x^-_i$, then it is not a subsequence of any individual $x^-_i$.

So you could try many different ways of randomly interleaving the $n$ strings $x^−_i$ into a single string, and for each such interleaving $y_j$, look for the shortest subsequence $z_j$ of $x^+$ that avoids being a subsequence of $y_j$ using Aryabhata's nice DP algorithm for the two-string case, and pick whichever $z_j$ is shortest over all interleavings you tried.

Caveat: No guarantee of optimality even if we try all interleavings

Surprisingly (to me at least), even if you repeat the above procedure for all possible interleavings, you are not guaranteed to find the optimal solution: Consider the instance in which $x^+ = aaa$, $n=2$, and $x^-_1 = x^-_2 = a$. Then $aa$ is an optimal solution with length 2, but the shortest solution found by trying all interleavings of $x^-_1$ and $x^-_2$ is $aaa$, with length 3.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.