最长公共子序列,LCS,动态规划实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are: ["b", "a", "c", "a", "a", "b", "d"] and ["a", "c", "a", "c", "a", "a", "b"] #The Longest-Commom-Subsequence is: a c a a b chars = ( "a" .. "e" ).to_a x, y = [], [] 1 .upto(rand( 5 ) + 5 ) { |i| x << chars[rand(chars.size- 1 )] } 1 .upto(rand( 5 ) + 5 ) { |i| y << chars[rand(chars.size- 1 )] } printf( "The random character arrays are: %s and %s\n" , x, y) c = Array . new (x.size + 1 ){ Array . new (y.size + 1 )} b = Array . new (x.size + 1 ){ Array . new (y.size + 1 )} def LCS_length(x, y ,c ,b) m, n = x.size, y.size ( 0 ..m). each {|i| c[i][ 0 ] = 0 } ( 0 ..n). each {|j| c[ 0 ][j] = 0 } for i in ( 1 ..m) do for j in ( 1 ..n) do if (x[i - 1 ] == y [j - 1 ]) c[i][j] = c[i - 1 ][j - 1 ] + 1 ; b[i][j] = 0 else if (c[i - 1 ][j] >= c[i][j - 1 ]) c[i][j] = c[i - 1 ][j] b[i][j] = 1 else c[i][j] = c[i][j - 1 ] b[i][j] = 2 end end end end end def Print_LCS(x, b, i, j) return if (i == 0 || j == 0 ) if (b[i][j] == 0 ) Print_LCS(x, b, i- 1 , j- 1 ) printf( "%c " , x[i - 1 ]) elsif (b[i][j] == 1 ) Print_LCS(x, b, i- 1 , j) else Print_LCS(x, b, i, j- 1 ) end end LCS_length(x, y, c ,b) print "The Longest-Commom-Subsequence is: " Print_LCS(x, b, x.size, y.size) |