2
$\begingroup$

Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I can't figure out how to get a bound lower than $O(2^n)$.

My recurrence (it's $O(2^n)$ with memoization) --

Consider the string to be $A[1 .. n]$. And consider the substring $A[1 .. i]$ for $i < n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A[1 .. i+1]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same. To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A[i+1]$ included in them, as well as the entire substring $A[1 .. i+1]$.

This last thing can be memoized. That is, the end point of the entire substring $A[1 .. i]$ can be memoized. So when we need to check if $A[1 .. i+1]$ works, we just need to go to the next state after reading $A[i+1]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example: Consider the string $a_1a_2a_3a_4$.

$a_1$:
Takes $O(1)$ to check. Then memoize.

$a_1a_2$:
Check $a_2$. Takes $O(1)$. Then memoize.
Check $a_1a_2$. Takes $O(1)$ as checking $a_1$ was previously memoized. Then memoize.

$a_1a_2a_3$:
Check $a_3$: Takes $O(1)$. Then memoize.
Check $a_1a_3$, $a_2a_3$: takes $O(1)$ per check, as $a_1$, $a_2$ were previously memoized. Then memoize. Check $a_1a_2a_3$: Takes $O(1)$ as checking $a_1a_2$ was previous memoized.

$a_1a_2a_3a_4$:
Check $a_4$: Takes $O(1)$. Then memoize.
Check $a_1a_4$, $a_2a_4$, $a_3a_4$: takes $O(1)$ per check, as $a_1$, $a_2$, $a_3$ were previously memoized.
Check $a_1a_2a_4$, $a_1a_3a_4$, $a_2a_3a_4$: takes $O(1)$ per check, as $a_1a_2$, $a_1a_3$, $a_2a_3$ were previously memoized.
Check $a_1a_2a_3a_4$: takes $O(1)$ as $a_1a_2a_3$ was previously memoized.

$\endgroup$
  • $\begingroup$ It could be the case you're looking for a sub_string_ instead of a sub_sequence_ (those are different). Could you confirm whether you indeed want a subsequence ? $\endgroup$ – Discrete lizard Mar 10 '18 at 19:09
  • 1
    $\begingroup$ Yeah I definitely want a subsequence, not a substring. @Discretelizard $\endgroup$ – picotard Mar 10 '18 at 19:15
  • $\begingroup$ What have you tried? What decomposition into subproblems have you considered? Where did you get stuck? I suggest you start with our general advice for dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 10 '18 at 20:56
  • $\begingroup$ Please don't use "stuff. EDIT: more stuff". Instead, revise the question to read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. $\endgroup$ – D.W. Mar 11 '18 at 18:24
1
$\begingroup$

You can add an extra parameter $s$, which represents a state of the DFA, for your dynamic programming.

Let $f(i,s)$ be the length of the longest subsequence of $A[1\ldots i]$ accepted by a DFA obtained by changing the end state of the primary DFA to $s$. Now $f(i+1,s)$ can be computed by comparing $f(i,s)$ (representing $A[i+1]$ is not chosen) and $f(i,t)+1$ (representing $A[i+1]$ is chosen) for each state $t$ that transforms to $s$ when reading $A[i+1]$.

But note, the time complexity this algorithm is not bounded by $O(qn)$ because we may have to check no more than constant $f(i,t)$'s for each computation. A simple improvement is to consider $A[i\ldots n]$ instead of $A[1\ldots i]$. Now $f(i,s)$ represents the length of the longest subsequence of $A[i\ldots n]$ accepted by a DFA obtained by changing the start state of the primary DFA to $s$, and $f(i,s)$ can be computed by comparing $f(i+1,s)$ and $f(i+1,t)+1$ where $s$ transforms to $t$ when reading $A[i]$. Now the running time is improved to $O(qn)$.

$\endgroup$
  • $\begingroup$ I'm sorry, I don't understand this at all. And how this modifies my algorithm to make it O(qn) $\endgroup$ – picotard Mar 11 '18 at 6:48
  • $\begingroup$ @Kek Which part don't you understand? Maybe you can consider it as a totally different algorithm from yours. The main difference is that it computes $f(i,s)$ while your algorithm computes $f(i)$. $\endgroup$ – xskxzr Mar 11 '18 at 7:39

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.