贪婪的LCS Java代码实现
提问于 2014-05-31 21:11:31
我试图从这个日志中编写java代码：
此代码是一种贪婪的方法，用于计算非洲裔longest的最长公共子序列。
下面是我的编辑的代码：
public class LCS_Greedy {
public static void main(String[] args) {
// String X_awal = "ABCBDABE";
// String Y = "BDCABA";
// String X_awal = "XMJYAUZ";
// String Y = "MZJAWXU";
// String X_awal ="AGGTAB";
// String Y="GXTXAYB";
// String X_awal = "ABCDGH";
// String Y = "AEDFHR";
// String X_awal = "AHBCDG";
// String Y = "AEDFHR";
//greedy not always optimum
String X_awal = "bcaaaade";
String Y = "deaaaabc";
String X = match(X_awal, Y);
int[] Penanda_Y = new int[Y.length()];
int y_length = Y.length();
for (int k = 0; k < y_length; k++) {
Penanda_Y[k] = 0;
}
int m = X.length();
int n = Y.length();
String L = "";
String LSym = "";
int R = 0;
int i = 1;
int[] P = new int[100];
P[i] = posisi(X, Y, i, Penanda_Y, R);
i = 1;
while (i <= m) {
if (i != m) {
P[i + 1] = posisi(X, Y, (i + 1), Penanda_Y, R);
}
if (P[i + 1] == 0) {
if (P[i] > R) {
L = L + " " + Integer.toString(P[i]);
LSym = LSym + " " + X.charAt(i - 1);
}
break;
}
if (P[i + 1] < R || P[i] < R) {
R = 0;
}
if (P[i] > P[i + 1]) {
if (R == 0 && i > 1) {
L = L + " " + Integer.toString(P[i]);
LSym = LSym + " " + X.charAt(i - 1);
Penanda_Y[P[i] - 1] = 1;
R = P[i];
i = i + 1;
if (R == Y.length() || i > X.length()) {
break;
}
P[i] = posisi(X, Y, i, Penanda_Y, R);
} else {
L = L + " " + Integer.toString(P[i + 1]);
LSym = LSym + " " + X.charAt(i + 1 - 1);
Penanda_Y[P[i + 1] - 1] = 1;
R = P[i + 1];
i = (i + 1) + 1;
if (R == Y.length() || i > X.length()) {
break;
}
P[i] = posisi(X, Y, i, Penanda_Y, R);
}
} else {
if (R == 0 && i > 1) {
L = L + " " + Integer.toString(P[i + 1]);
LSym = LSym + " " + X.charAt(i + 1 - 1);
Penanda_Y[P[i + 1] - 1] = 1;
R = P[i + 1];
i = (i + 1) + 1;
if (R == Y.length() || i > X.length()) {
break;
}
P[i] = posisi(X, Y, i, Penanda_Y, R);
} else {
L = L + " " + Integer.toString(P[i]);
LSym = LSym + " " + X.charAt(i - 1);
Penanda_Y[P[i] - 1] = 1;
R = P[i];
i = i + 1;
if (R == Y.length() || i > X.length()) {
break;
}
P[i] = posisi(X, Y, i, Penanda_Y, R);
}
}
}
System.out.println("X = " + X_awal);
System.out.println("X = " + Y);
System.out.println("L = " + L);
System.out.println("LSym = " + LSym);
System.out.println("Length = " + LSym.length() / 2);
}
public static String match(String X, String Y) {
String hasil = "";
for (int i = 0; i < X.length(); i++) {
for (int j = 0; j < Y.length(); j++) {
if (X.charAt(i) == Y.charAt(j)) {
hasil = hasil + X.charAt(i);
break;
}
}
}
return hasil;
}
public static int posisi(String X, String Y, int i, int[] Penanda_Y, int R) {
int n = Y.length();
int k;
int kr = 0;
i = i - 1;
for (k = 0; k < n; k++) {
if ((X.charAt(i) == Y.charAt(k)) && Penanda_Y[k] == 0) {
kr = k + 1;
break;
}
}
for (k = R; k < n; k++) {
if ((X.charAt(i) == Y.charAt(k)) && Penanda_Y[k] == 0) {
kr = k + 1;
break;
}
}
return kr;
}
}但是当我运行那个程序时，在某些情况下它有真正的输出，但在另一个情况下它是假的。那密码怎么了？有人能跟我解释一下吗？谢谢
编辑：
我的代码现在可以完美地运行，但它似乎远离了日志中的伪代码。有人能解释一下吗？为什么我不能准确地从日志中生成代码？当我从日记中给出的伪代码生成时，总是会出错。谢谢。
回答 1
Stack Overflow用户
发布于 2015-05-06 06:22:17
该算法不会导致LCS。贪婪的猜测是错误的。它假设早期的比赛将保证形成LCS。尽管伪码采用了X中前两个子串的早期匹配，这可能会在Y开头跳过许多常见的子字符串。另一个简单的测试是将X中的最后一个'E‘改为'A’，该算法将无法确定地找到最后匹配的'A‘。事实是，早期的比赛可能会锁定位置，以禁止更长的比赛。换句话说，我们可能需要跳过一些早期的匹配，以便我们可以找到一个更长的匹配。从数学上证明了动态规划方法的正确性，但该算法没有实现。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23976954
复制
腾讯云开发者
