Longest common subsequence: Difference between revisions
(New page: {{puzzle}}The '''longest common subsequence''' (or '''LCS''') of groups A and B is the longest group of elements from A and B that are common between the two groups and in the same order i...) |
(→{{header|Java}}: added dynamic programming solution) |
||
Line 21: | Line 21: | ||
return (x.length() > y.length()) ? x : y; |
return (x.length() > y.length()) ? x : y; |
||
} |
} |
||
}</java> |
|||
A dynamic programming solution: |
|||
<java>public static String lcs(String a, String b) { |
|||
int[][] lengths = new int[a.length()+1][b.length()+1]; |
|||
// row 0 and column 0 are initialized to 0 already |
|||
for (int i = 0; i < a.length(); i++) |
|||
for (int j = 0; j < b.length(); j++) |
|||
if (a.charAt(i) == b.charAt(j)) |
|||
lengths[i+1][j+1] = lengths[i][j] + 1; |
|||
else |
|||
lengths[i+1][j+1] = |
|||
Math.max(lengths[i+1][j], lengths[i][j+1]); |
|||
// read the substring out from the matrix |
|||
StringBuffer sb = new StringBuffer(); |
|||
for (int x = a.length(), y = b.length(); |
|||
x != 0 && y != 0; ) { |
|||
if (lengths[x][y] == lengths[x-1][y]) |
|||
x--; |
|||
else if (lengths[x][y] == lengths[x][y-1]) |
|||
y--; |
|||
else { |
|||
assert a.charAt(x-1) == b.charAt(y-1); |
|||
sb.append(a.charAt(x-1)); |
|||
x--; |
|||
y--; |
|||
} |
|||
} |
|||
return sb.reverse().toString(); |
|||
}</java> |
}</java> |
Revision as of 03:20, 8 May 2008
The longest common subsequence (or LCS) of groups A and B is the longest group of elements from A and B that are common between the two groups and in the same order in each group. For example, the sequences "1234" and "1224533324" have an LCS of "1234":
1234 1224533324
For a string example, consider the sequences "thisisatest" and "testing123testing". An LCS would be "tsitest":
thisisatest testing123testing
In this puzzle, your code only needs to deal with strings. Write a function which returns an LCS of two strings (case-sensitive). You don't need to show multiple LCS's.
Java
This is not a particularly fast algorithm, but it gets the job done eventually. The speed is a result of many recursive functions calls.
<java>public static String lcs(String a, String b){
if(a.length() == 0 || b.length() == 0){ return ""; }else if(a.charAt(a.length()-1) == b.charAt(b.length()-1)){ return lcs(a.substring(0,a.length()-1),b.substring(0,b.length()-1)) + a.charAt(a.length()-1); }else{ String x = lcs(a, b.substring(0,b.length()-1)); String y = lcs(a.substring(0,a.length()-1), b); return (x.length() > y.length()) ? x : y; }
}</java>
A dynamic programming solution: <java>public static String lcs(String a, String b) {
int[][] lengths = new int[a.length()+1][b.length()+1];
// row 0 and column 0 are initialized to 0 already
for (int i = 0; i < a.length(); i++) for (int j = 0; j < b.length(); j++) if (a.charAt(i) == b.charAt(j)) lengths[i+1][j+1] = lengths[i][j] + 1; else lengths[i+1][j+1] = Math.max(lengths[i+1][j], lengths[i][j+1]);
// read the substring out from the matrix StringBuffer sb = new StringBuffer(); for (int x = a.length(), y = b.length(); x != 0 && y != 0; ) { if (lengths[x][y] == lengths[x-1][y]) x--; else if (lengths[x][y] == lengths[x][y-1]) y--; else { assert a.charAt(x-1) == b.charAt(y-1); sb.append(a.charAt(x-1)); x--; y--; } }
return sb.reverse().toString();
}</java>