# Dynamic programming - build string that subsequence of $s_1$ and substring of $s_2$ - optimum solution [closed]

Hi I can't find an algorithm to solve this problem Given two string $$s_1,s_2$$ and for every character $$c$$ there is a value $$f(c)$$, value of string defined to be the sum of all values of the characters in the string. Build a string $$s$$ with maximum value such that $$s$$ is a subsequence of $$s_1$$ and $$s$$ is substring of $$s_2$$ How can i find the maximum solution?

• your question is still unclear. you haven't answered @GerryMyerson's question "value of a string", is it the sum of the values of the character in the string? – kodlu Dec 2 at 23:10
• Also: if your strings $s_1$ and $s_2$ are finite, then a simple algorithm is to look at every subsequence of $s_1$ and every substring of $s_2$ and find all the matches, and then compute all the corresponding values, and pick the biggest one. If $s_1$ and $s_2$ are infinite, then it's not clear to me that an algorithm even exists, since the farther you look, the better a satisfactory string $s$ you might find. So I think some further clarification is needed. – Gerry Myerson Dec 3 at 0:07
• You can assume that they are finite – miki6846 Dec 3 at 7:28
• Yes but im looking for dynamic programming based algorithm, that probably will be more efficient – miki6846 Dec 3 at 15:16
• Then let me suggest that you edit that into the body of your question. People shouldn't have to dig through the comments to figure out what the question is. – Gerry Myerson Dec 4 at 0:55