Longest subsequence accepted by DFA (Dynamic Prog algorithm)

Question

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.

Answer 1

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)$.