Longest Common subsequence

Panphobia · **Posted:** Tue Dec 11, 2012 9:22 pm

I am doing some questions my teacher gave me, since there is not going to be a dwite next week, basically finding when strings match if you take characters out, and this is the longest match, i tried to code up a longest common subsequence algorithm and it isnt working for some weird reason, if you could point it out that would be nice Very Happy

code:

package palindrome;
public class Palindrome {
static int[][]c;
public static void main(String[] args) {
String forwards = "losdfosfgdfgfdfgdgdfgdfgvs";
String backwards = "wassduppsfdmyniasd";
char[] forwa = new char[forwards.length()];
char[] back = new char[backwards.length()];
for (int i = 0; i < forwa.length; ++i) {
forwa[i] = forwards.charAt(i);
}
for (int i = 0; i < back.length; ++i) {
back[i] = backwards.charAt(i);
}
System.out.println(lcs(forwa, back));
}
public static int lcs(char[] forward, char[] backward) {
c = new int[forward.length][backward.length];
for (int i = 0; i < forward.length; ++i) {
c[i][0] = 0;
}
for (int i = 0; i < backward.length; ++i) {
c[0][i] = 0;
}
for (int i = 0; i < forward.length; ++i) {
for (int j = 0; j < backward.length; ++j) {
if (forward[i] == backward[j]) {
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
}
}
}
return c[forward.length-1][backward.length-1];
}
}

DemonWasp · **Posted:** Wed Dec 12, 2012 1:17 am

Why not debug it yourself? Here's some hints to get you started:

Simplify your inputs. Set forwards="a" and backwards="ab". That makes the answer obvious: it should be "a" (or 1, the way you've set it up).

In lcs(), right before the return statement, output the contents of the array. Did you get what you expected to get? Why or why not?

Panphobia · **Posted:** Wed Dec 12, 2012 3:57 pm

yea I know now, the problem was the for loop starting at 0 Razz

, ok so the problem now is not the actual error, its the output sadly i tested it with a simple word and it just outputs the word length, a hint would be nice, by the way im trying to check when a word becomes a palindrome after taking away x amount of letters, by reversing the string and lcs of them both

code:

package palindrome;

import java.io.*;
import java.util.*;

public class Palindrome {

static int[][] c;

public static void main(String[] args) throws FileNotFoundException {
Scanner s = new Scanner(new File("/home/daniel/NetBeansProjects/Palindrome/src/palindrome/DATA5.txt"));
//while (s.hasNext()) {
String forwards = "hello";
char[] forwa = new char[forwards.length()];
char[] back = new char[forwards.length()];
for (int i = 0; i < forwards.length(); ++i) {
forwa[i] = forwards.charAt(i);
}
for (int i = forwards.length() - 1; i >= 0; --i) {
back[i] = forwards.charAt(i);
System.out.print(back[i]);
}
System.out.println(lcs(forwa, back));
// }
}

public static int lcs(char[] forward, char[] backward) {
c = new int[forward.length][backward.length];
for (int i = 0; i < forward.length; ++i) {
c[i][0] = 0;
}
for (int i = 0; i < backward.length; ++i) {
c[0][i] = 0;
}
for (int i = 1; i < forward.length; ++i) {
for (int j = 1; j < backward.length; ++j) {
if (forward[i] == backward[j]) {
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
}
}
}
return c[forward.length - 1][backward.length - 1] + 1;
}
}

Panphobia · **Posted:** Thu Dec 13, 2012 12:18 am

Still cant figure out why it wont do what I want it to, like I said I want to take in a value, reverse it, find the lowest common subsequence of both it and it reversed to see how many letters you need to pull out of the word to make it a palindrome

DemonWasp · **Posted:** Thu Dec 13, 2012 11:57 am

Read about the "trace-back approach" on Wikipedia: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Traceback_approach . That's what you need to use to find the letters that the two strings have in common.

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members