hello
I'm trying to make a program
that allows you to return and calculate the shortest common supersecuence using dynamic programming.
The basic ideas of supersecuence common Shortest
to search a given set of strings for example L, the smallest chain, which is one for each string supersecuence L.
the problem I have not returned to me or the chain or the length
well I do not know what is going wrong I attached what I have done so far.
/ / Fill the array using prog.dinámica:
private int aux[][];
int longr = r.length();
int longt = t.length();
aux = new int[longr + 1][longt + 1];
for (int i = 0; i <= longr; i++) {
m[i][0] = i;
aux[i][0] = -1;
}
for (int j = 0; j <= longt; j++) {
m[0][j] = j;
aux[0][j] = 1;
}
for (int j = 1; j <= longt; j++) {
for (int i = 1; i <= longr; i++) {
if (r.charAt(longr - i) == t.charAt(longt - j)) {
m[i][j] = m[i - 1][j - 1] + 1;
aux[i][j] = 0;
} else {
m[i][j] = Math.min(m[i - 1][j], m[i][j - 1]) + 1;
if (m[i - 1][j] <= m[i][j - 1]) {
aux[i][j] = -1;
} else {
aux[i][j] = 1;
}
}
}
}
}
method returns the string i thkink it's wrong
public String unaSolución() {
int lonr = r.length(), lonj = t.length();
int i = r.length(), j = t.length();
String cad = "";
while (i > 0 || j > 0) {
if (aux[i][j] == 0) {
cad = cad + r.charAt(lonr - i);
i = i - 1;
j = j - 1;
} else if (aux[i][j] == -1) {
cad = cad + r.charAt(lonr - i);
i = i - 1;
} else {
cad = cad + t.charAt(lonj - j);
j = j - 1;
}
}
return cad;
}
In anticipation of your help
Yours sincerely
thank u