-2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – kodlu Dec 2 at 23:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Dec 3 at 0:07
  • 1
    $\begingroup$ You can assume that they are finite $\endgroup$ – miki6846 Dec 3 at 7:28
  • 1
    $\begingroup$ Yes but im looking for dynamic programming based algorithm, that probably will be more efficient $\endgroup$ – miki6846 Dec 3 at 15:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Dec 4 at 0:55