Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

Anyone?

You have 3 states:

dp[position on the first string][position on the second string][where you are on the virus]

dp[i][j][k]

if k == virus.size() return -INF, if i == first.size() || j==second.size() return 0

then you take the maximum between

dp[i+1][j][k], dp[i][j+1][k] and if first[i]==second[j] you can take it and and you'll have 1 + dp[i+1][j+1][next_k]. You need to use KMP to know what's the next_k depending on the letter you are taking. Make an array that will remember which choice you took on each step and you can run through the memoization to get the answer.

Notice that the optimal subsequence will be a subsequence of the longest common subsequence. Then, it is a good idea to obtain the longest common subsequence using Needleman-Wunsch (use cost for mismatch equal to infinity and deletions/insertions cost 0) or other equivalent algorithm. Once you have this LCS, use a longest increasing subsequence-like approach in order to know the answer.